Submission #1167884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167884		FedShat	Matching (COCI20_matching)	C++20	0 / 110	0 ms	328 KiB

matching

#include <bits/stdc++.h>
#define int long long

using namespace std;
const long long inf = 1e18 + 7;
vector<vector<int>> g;
vector<bool> used;
vector<int> pr;

bool dfs(int v){
    if(used[v]){
        return false;
    }
    used[v] = true;
    for(auto u: g[v]){
        if(pr[u] == -1 || dfs(pr[u])){
            pr[u] = v;
            pr[v] = u;
            return true;
        }
    }
    return false;
}

signed main(){
#ifdef rog
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;
    g.resize(n);
    used.resize(n);
    pr.resize(n, -1);

    vector<pair<int, int>> arr(n);
    for(int i = 0;i < n;i++){
        cin >> arr[i].first >> arr[i].second;
    }

    for(int i = 0;i < n;i++){
        for(int j = i + 1;j < n;j++){
            if(arr[i].first == arr[j].first || arr[i].second == arr[j].second){
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }

    bool fl = true;
    for(int i = 0;i < n;i++){
        if(pr[i] == -1){
            used = vector<bool>(n, false);
            if(!dfs(i)){
                fl = false;
                break;
            }
        }
    }

    if(fl){
        cout << "DA" << endl;
        for(int i = 0;i < n;i++){
            if(pr[i] > i){
                cout << i + 1 << " " << pr[i] + 1 << endl;
            }
        }
    }else{
        cout << "NE" << endl;
    }

    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 40
• Subtask 5: 0 / 52