Submission #223455

#	Time	Username	Problem	Language	Result	Execution time	Memory
223455		lyc	Matching (COCI20_matching)	C++14	5 / 110	333 ms	524292 KiB

matching

#include <bits/stdc++.h>
using namespace std;

#define SZ(x) (int)(x).size()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

const int MX_N = 1e5+5;
const int MX_X = 1e6+5;

int N, X[MX_N], Y[MX_N];

vector<int> atX[MX_N], atY[MX_N];
vector<int> xs, ys;

struct UnionFind {
    vector<int> sz, p;
    UnionFind(int n) { sz.assign(n,1); p.assign(n,0); iota(p.begin(),p.end(),0); }
    int findset(int i) { return (p[i] == i) ? i : (p[i] = findset(p[i])); }
    bool unionset(int i, int j) {
        int x = findset(i), y = findset(j);
        if (x != y) {
            if (sz[x] < sz[y]) swap(x,y);
            p[y] = x;
            sz[x] += sz[y];
            return true;
        } return false;
    }
};

vector<int> al[MX_N];
int matched[MX_N], vis[MX_N];

void dfs(int u, int x) { vis[u] = x; for (int v : al[u]) if (vis[v] != 1) dfs(v,x); }

bool ok;
void assign(int u, int x) {
    //cout << "assign " << u << " :: " << SZ(al[u]) << endl;
    vis[u] = 2;
    if (x == 0) {
        if (SZ(atX[X[u]]) == 1) { ok = 0; return; }
        //cout << "hi" << endl;
        int v = atX[X[u]][0] ^ atX[X[u]][1] ^ u;
        matched[u] = v;
        matched[v] = u;
    } else {
        if (SZ(atY[u]) == 1) { ok = 0; return; }
        int v = atY[Y[u]][0] ^ atY[Y[u]][1] ^ u;
        matched[u] = v;
        matched[v] = u;
    }
    for (int v : al[u]) if (vis[v] == 0) assign(v,x);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    FOR(i,1,N){
        cin >> X[i] >> Y[i];
        atX[X[i]].push_back(i);
        atY[Y[i]].push_back(i);
        xs.push_back(X[i]);
        ys.push_back(Y[i]);
    }

    sort(xs.begin(),xs.end()); xs.resize(unique(xs.begin(),xs.end())-xs.begin());
    sort(ys.begin(),ys.end()); ys.resize(unique(ys.begin(),ys.end())-ys.begin());

    UnionFind UF(N+1);
    for (int x : xs) {
        if (SZ(atX[x]) > 1) {
            UF.unionset(atX[x][0],atX[x][1]);
            int y0 = min(Y[atX[x][0]],Y[atX[x][1]]);
            int y1 = max(Y[atX[x][0]],Y[atX[x][1]]);
            for (int y : ys) if (y0 < y && y < y1) {
                if (SZ(atY[y]) > 1) {
                    int x0 = min(X[atY[y][0]],X[atY[y][1]]);
                    int x1 = max(X[atY[y][0]],X[atY[y][1]]);
                    if (x0 < x && x < x1) {
                        UF.unionset(atX[x][0],atY[y][0]);
                    }
                }
            }
        }
    }
    for (int y : ys) if (SZ(atY[y]) > 1) UF.unionset(atY[y][0],atY[y][1]);

    //FOR(i,1,N) cout << UF.findset(i) << ' ';
    //cout << endl;

    FOR(i,1,N) FOR(j,i+1,N) if (UF.findset(i) == UF.findset(j)) {
        al[i].push_back(j);
        al[j].push_back(i);
    }

    memset(matched,-1,sizeof matched);
    memset(vis,0,sizeof vis);
    FOR(i,1,N) if (!vis[i]) {
        ok = 1; assign(i,0);
        if (ok) dfs(i,1);
        else {
            dfs(i,0);
            ok = 1; assign(i,1);
            if (ok) dfs(i,1);
            else {
                cout << "NE" << '\n';
                return 0;
            }
        }
    }

    cout << "DA" << '\n';
    FOR(i,1,N) if (matched[i] > i) cout << i << " " << matched[i] << '\n';
}

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