Submission #212733

#	Time	Username	Problem	Language	Result	Execution time	Memory
212733		egorlifar	Matching (COCI20_matching)	C++17	58 / 110	2578 ms	40960 KiB

matching

#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
 
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define rank rank228
#define y1 y1228
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define mp make_pair
using ll = long long;
using ld = long double;
// const int MAXMEM = 200 * 1000 * 1024;
// char _memory[MAXMEM];
// size_t _ptr = 0;
// void* operator new(size_t _x) { _ptr += _x; return _memory + _ptr - _x; }
// void operator delete (void*) noexcept {}
const string FILENAME = "input";
const int MAXN = 100205;


int n;
int x[MAXN], y[MAXN];
vector<vector<int> > whox, whoy;
bool hor[MAXN], ver[MAXN];
int parent[MAXN];


int findset(int a) {
    if (a == parent[a]) {
        return a;
    }
    return parent[a] = findset(parent[a]);
}



void unite(int a, int b) {  
    a = findset(a);
    b = findset(b);
    if (a == b) {
        return;
    }
    parent[a] = b;
}


int ss = 1;
vector<int> who[MAXN * 7];
  
struct node
{
    int who = 0;
    int cntalive = 0;
    bool odnacomponenta = true;
};
  
  
node d[MAXN * 8];
  
node operator +(const node &a, const node &b) {
    if (!a.cntalive) {
        return b;
    }
    if (!b.cntalive) {
        return a;
    }
    node c;
    c.cntalive = a.cntalive + b.cntalive;
    c.who = a.who;
    c.odnacomponenta = a.odnacomponenta & b.odnacomponenta & (a.who == b.who);
    return c;
}
  
  
void del(int i) {
    i += ss;
    d[i].cntalive = 0;
    d[i].who = 0;
    d[i].odnacomponenta = false;
    while (i >> 1 > 0) {
        i >>= 1;
        d[i] = d[i * 2] + d[i * 2 + 1];
    } 
}
  
  
void change(int i, int comp) {
    i += ss;
    d[i].cntalive = 1;
    d[i].who = comp;
    d[i].odnacomponenta = true;
    while (i >> 1 > 0) {
        i >>= 1;
        d[i] = d[i * 2] + d[i * 2 + 1];
    } 
}
 
int cur[MAXN * 2];
 
  
  
void tryunite(int v, int vl, int vr, int l, int r, int x) {
    if (!d[v].cntalive) {
        return;
    }
    if (vl > r || vr < l) {
        return;
    }
    if (l <= vl && vr <= r) {
       // cout << "opa" << ' ' << vl << ' ' << vr << endl;
        if (d[v].odnacomponenta) {
           // cout << "kek" << endl;
            int t = findset(x);
            if (t != x) {
                int b=  findset(d[v].who);
              //  cout << x << ' '  << t << ' ' << b << endl;
                if (t != b) {
                    int g = sz(who[t]);
                    int g1 = sz(who[b]);
                    int a = t;
                    if (g < g1) {
                        swap(a, b);
                    }
                    parent[b] = a;
                    //cout << a << ' ' << b << endl;
                    for (auto x: who[b]) {
                        if (cur[x] != -1 && findset(cur[x]) == a) {
                            who[a].pb(x);
                            change(x, a);
                        }
                    }
                    who[b].clear();
                    who[b].shrink_to_fit();
                }
            } else {
                parent[x] = findset(d[v].who);
            }
        } else {
            tryunite(v * 2, vl, (vl + vr) / 2, l, r, x);
            tryunite(v * 2 + 1, (vl + vr) / 2 + 1, vr, l, r, x);
        }
        return;
    }
    tryunite(v * 2, vl, (vl + vr) / 2, l, r, x);
    tryunite(v * 2 + 1, (vl + vr) / 2 + 1, vr, l, r, x);
}


int valh[MAXN], valv[MAXN];
vector<pair<pair<int, int>, int> > fs[MAXN];
vector<pair<pair<int, int>, int> > mx[MAXN];
int cnt[MAXN][2];
int col[MAXN];


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   // read(FILENAME);     
    cin >> n;
    whox.resize(100001);
    whoy.resize(100001);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        whox[x[i]].pb(i);
        whoy[y[i]].pb(i);
        parent[i] = i;
    }
    vector<pair<int, int> > vs, hs;
    for (auto xx: whox) {
        if (sz(xx) == 2) {
            for (auto y: xx) {
                ver[y] = true;
                valv[y] = xx[0] ^ xx[1];
            }
            unite(xx[0], xx[1]);
            if (y[xx[0]] > y[xx[1]]) {
                swap(xx[0], xx[1]);
            }
            int t = findset(xx[0]);
            fs[y[xx[0]]].pb({mp(x[xx[0]], t), 1});
            fs[y[xx[1]]].pb({mp(x[xx[0]], t), -1});
        } 
    }
    for (auto xx: whoy) {
        if (sz(xx) == 2) {
            for (auto y: xx) {
                hor[y] = true;
                valh[y] = xx[0] ^ xx[1];
            }
            unite(xx[0], xx[1]);
            int t = findset(xx[0]);
            mx[y[xx[0]]].pb(mp(mp(x[xx[0]], x[xx[1]]), t));
        } 
    }
    for (int i = 0; i < n; i++) {
        if (!ver[i] && !hor[i]) {
            cout << "NE\n";
            exit(0);
        }
    }
    ss = 1;
    while (ss <= 100000) {
        ss <<= 1;
    }
    for (int i = 0; i <= 100000; i++) {
        for (auto x: fs[i]) {
            if (x.second == -1) {
             //   who[findset(cur[x.first.first])].erase(x.first.first);
                cur[x.first.first] = -1;
                del(x.first.first);
            }
        }
        for (auto x: fs[i]) {
            if (x.second == 1) {
                cur[x.first.first] = x.first.second;
                who[x.first.second].pb(x.first.first);
                change(x.first.first, x.first.second);
            }
        }
        for (auto x: mx[i]) {
            int l = x.first.first;
            int r = x.first.second;
            if (l > r) {
                swap(l, r);
            }
            tryunite(1, 1, ss, l + 1, r + 1, x.second);
        }
    }
    for (int i = 0; i < n; i++) {
        if (!ver[i]) {
            cnt[findset(i)][1]++;
        }
        if (!hor[i]) {
            cnt[findset(i)][0]++;
        }
    }
    for (int i = 0; i < n; i++) {
        if (findset(i) == i) {
            if (cnt[i][0] && cnt[i][1]) {
                cout << "NE\n";
                return 0;
            }
            col[i] = cnt[i][0] ? 0: 1;
        }
    }
    cout << "DA\n";
    for (int i = 0; i < n; i++) {
        int t = col[findset(i)];
        int f = 0;
        if (t == 0) {
            f = valv[i] ^ i;
        } else {
            f = valh[i] ^ i;
        }
        if (f > i) {
            assert(i != f);
            cout << i + 1 << ' ' << f + 1 << '\n';
        }
    }
    return 0;
}               

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