Submission #1167822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167822		FedShat	Matching (COCI20_matching)	C++20	58 / 110	2595 ms	23560 KiB

matching

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

vector<vector<int>> g;

vector<int> clr;

int clrs = 0;

vector<int> st;
vector<bool> inSt;

int t;
vector<int> up;

void dfs(int v){
    int tin = t++;
    up[v] = tin;
    st.push_back(v);
    inSt[v] = true;

    for(int u : g[v]){
        if(clr[u] == -1 && !inSt[u]){
            dfs(u);
        }
        if(inSt[u]){
            up[v] = min(up[v], up[u]);
        }
    }
    if(up[v] == tin){
        while(st.back() != v){
            int u = st.back();
            st.pop_back();
            inSt[u] = false;
            clr[u] = clrs;
        }
        inSt[v] = false;
        clr[v] = clrs;
        st.pop_back();
        clrs++;
    }
}

vector<pair<int, int>> points;

struct line{
    int x1, y1, x2, y2;
    int ind1, ind2;
    line(int ind1_, int ind2_){
        ind1 = ind1_;
        ind2 = ind2_;

        x1 = points[ind1].first;
        x2 = points[ind2].first;
        y1 = points[ind1].second;
        y2 = points[ind2].second;

        if(x1 > x2) swap(x1, x2);
        if(y1 > y2) swap(y1, y2);
    }
};

bool check(line hor, line vert){
    return hor.x1 < vert.x1 && vert.x1 < hor.x2 && vert.y1 < hor.y1 && hor.y1 < vert.y2;
}

int vertvertices;

void preparesat(int vert_, int hor_){
    g.resize((vert_ + hor_) * 2);
    vertvertices = vert_;
}

int vertical(int v){
    return v * 2;
}
int nvertical(int v){
    return v * 2 + 1;
}
int gorizontal(int v){
    return vertvertices * 2 + v * 2;
}
int ngorizontal(int v){
    return vertvertices * 2 + v * 2 + 1;
}

void solve(){
    int n;
    cin >> n;
    points.resize(n);
    vector<pair<int, int>> lines(n, {-1, -1});
    unordered_map<int, int> vert;
    unordered_map<int, int> hor;
    vector<line> vertlines;
    vector<line> horlines;
    for(int i = 0; i < n; i++){
        int x, y;
        cin >> x >> y;
        points[i].first = x;
        points[i].second = y;
        if(vert.find(x) != vert.end()){
            int j = vert[x];
            lines[i].first = vertlines.size();
            lines[j].first = vertlines.size();
            vertlines.push_back(line(i, j));
        }else{
            vert[x] = i;
        }
        if(hor.find(y) != hor.end()){
            int j = hor[y];
            lines[i].second = horlines.size();
            lines[j].second = horlines.size();
            horlines.push_back(line(i, j));
        }else{
            hor[y] = i;
        }
    }

    preparesat(vertlines.size(), horlines.size());
    for(int i = 0; i < n; i++){
        if(lines[i].first == -1 && lines[i].second == -1){
            cout << "NE\n";
            return;
        }else if(lines[i].first == -1){
            int v = gorizontal(lines[i].second);
            g[v + 1].push_back(v);
        }else if(lines[i].second == -1){
            int v = vertical(lines[i].first);
            g[v + 1].push_back(v);
        }else{
            int v = vertical(lines[i].first);
            int u = gorizontal(lines[i].second);
            g[u].push_back(v + 1);
            g[u + 1].push_back(v);
            g[v].push_back(u + 1);
            g[v + 1].push_back(u);
        }
    }

    for(int i = 0; i < horlines.size(); i++){

        for(int j = 0; j < vertlines.size(); j++){
            if(check(horlines[i], vertlines[j])){
                int v = gorizontal(i);
                int u = vertical(j);
                g[v].push_back(u + 1);
                g[u].push_back(v + 1);
            }
        }
    }

    int w = g.size();

    inSt.assign(w, false);
    clr.assign(w, -1);
    up.assign(w, -1);

    for(int i = 0; i < w; i++){
        if(clr[i] == -1){
            dfs(i);
        }
    }

    vector<pair<int, int>> ans;
    
    for(int i = 0; i < vertlines.size(); i++){
        int v = vertical(i);
        if(clr[v] == clr[v + 1]){
            cout << "NE\n";
            return;
        }else if(clr[v] < clr[v + 1]){
            ans.push_back({vertlines[i].ind1, vertlines[i].ind2});
        }
    }

    for(int i = 0; i < horlines.size(); i++){
        int v = gorizontal(i);
        if(clr[v] == clr[v + 1]){
            cout << "NE\n";
            return;
        }else if(clr[v] < clr[v + 1]){
            ans.push_back({horlines[i].ind1, horlines[i].ind2});
        }
    }

    cout << "DA\n";

    for(auto [a, b] : ans){
        cout << a + 1 << ' ' << b + 1 << '\n';
    }
}

signed main(){
    #ifdef LOCAL

    freopen("D:\\projects\\olymp\\input.txt", "r", stdin);
    freopen("D:\\projects\\olymp\\output.txt", "w", stdout);

    #endif
    
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

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