This can be accomplished using external IDs. I would recommend using dataweave before connecting to Salesforce and submitting the parent objects' external ids as seen below: (assuming the external ID values are present in the payload).
{ c_ext_id: payload.cExt, // Value: C's external ID from payload a__r: { a_ext_id: payload.aExt // value: A's External ID from payload }, b__r:{ b_ext_id: payload.bExt // value: B's External ID from payload }, status__c: payload.status }
Hope this helps!
Check out the Salesforce admin training to learn more about it.