Submission #201247

# Submission time Handle Problem Language Result Execution time Memory
201247 2020-02-10T03:19:52 Z gs14004 Matching (COCI20_matching) C++17
5 / 110
201 ms 157008 KB
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using pi = pair<int, int>;
using lint = long long;
const int MAXN = 100005;
const int MAXT = 2000005;
 
struct strongly_connected{
    vector<vector<int>> gph;
 
    void init(int n){
        gph.resize(n);
    }
 
    void add_edge(int s, int e){
        gph[s].push_back(e);
    }
 
vector<int> val, comp, z, cont;
int Time, ncomps;
template<class G, class F> int dfs(int j, G& g, F f) {
    int low = val[j] = ++Time, x; z.push_back(j);
    for(auto e : g[j]) if (comp[e] < 0)
        low = min(low, val[e] ?: dfs(e,g,f));
 
    if (low == val[j]) {
        do {
            x = z.back(); z.pop_back();
            comp[x] = ncomps;
            cont.push_back(x);
        } while (x != j);
        f(cont); cont.clear();
        ncomps++;
    }
    return val[j] = low;
}
template<class G, class F> void scc(G& g, F f) {
    int n = sz(g);
    val.assign(n, 0); comp.assign(n, -1);
    Time = ncomps = 0;
    for(int i=0; i<n; i++) if (comp[i] < 0) dfs(i, g, f);
}
 
int piv;
    void get_scc(int n){
        scc(gph, [&](vector<int> &v){});
        for(int i=0; i<n; i++){
            comp[i] = ncomps - comp[i];
        }
        piv = ncomps; 
    }
}scc;
 
struct twosat{
    strongly_connected scc;
    int n;
    void init(int _n){ scc.init(2*_n); n = _n; }
    int NOT(int x){ return x >= n ? (x - n) : (x + n); }
    void add_edge(int x, int y){
        if((x >> 31) & 1) x = (~x) + n;
        if((y >> 31) & 1) y = (~y) + n;
        scc.add_edge(x, y), scc.add_edge(NOT(y), NOT(x));
    }
    bool satisfy(vector<int> &res){
        scc.get_scc(2*n);
        for(int i=0; i<n; i++){
            if(scc.comp[i] == scc.comp[NOT(i)]) return 0;
            if(scc.comp[i] < scc.comp[NOT(i)]) res[i] = 0;
            else res[i] = 1;
        }
        return 1;
    }
}twosat;
 
struct point{
    int x, y, idx;
}a[MAXN];
 
int n, vis[MAXN], cmp;
vector<int> gph[MAXN];
 
struct edg{
    int i1, i2, cmp;
};
 
vector<pi> ev_in[MAXN];
vector<pi> ev_out[MAXN];
vector<edg> cur_insec[MAXN];
 
int ds[MAXN];
 
struct node{
    int l, r;
}tree[MAXT]; 
 
int newnode(){ return cmp++; }
int root[MAXN];
 
void init(int s, int e, int p){
    if(s == e) return;
    tree[p].l = newnode();
    tree[p].r = newnode();
    int m = (s+e)/2;
    init(s, m, tree[p].l);
    init(m+1, e, tree[p].r);
    twosat.add_edge(p, tree[p].l);
    twosat.add_edge(p, tree[p].r);
}
 
void upd(int pos, int s, int e, int prv, int cur, int val){
    if(s == e){
        if(~val) twosat.add_edge(cur, val);
        return;
    }
    int m = (s+e)/2;
    if(pos <= m){
        tree[cur].l = newnode();
        tree[cur].r = tree[prv].r;
        upd(pos, s, m, tree[prv].l, tree[cur].l, val);
    }
    else{
        tree[cur].r = newnode();
        tree[cur].l = tree[prv].l;
        upd(pos, m+1, e, tree[prv].r, tree[cur].r, val);
    }
    twosat.add_edge(cur, tree[cur].l);
    twosat.add_edge(cur, tree[cur].r);
}
 
void query(int s, int e, int ps, int pe, int p, int v){
    if(e < ps || pe < s) return;
    if(s <= ps && pe <= e){
        twosat.add_edge(v, p);
        return;
    }
    int pm = (ps+pe)/2;
    query(s, e, ps, pm, tree[p].l, v);
    query(s, e, pm+1, pe, tree[p].r, v);
}
 
void Do(vector<edg> &vert, vector<edg> &hori){
    for(auto &i : vert){
        ev_in[a[i.i1].y].emplace_back(a[i.i1].x, i.cmp);
        ev_out[a[i.i2].y + 1].emplace_back(a[i.i1].x, -1);
    }
    for(auto &i : hori){
        cur_insec[a[i.i1].y].push_back(i);
    }
    root[0] = newnode();
    init(1, 100000, root[0]);
    for(int i=1; i<MAXN; i++){
        int prv = root[i - 1];
        for(auto &j : ev_out[i]){
            int nxt = newnode();
            upd(j.first, 1, 100000, prv, nxt, j.second);
            prv = nxt;
        }
        for(auto &j : ev_in[i]){
            int nxt = newnode();
            upd(j.first, 1, 100000, prv, nxt, j.second);
            prv = nxt;
        }
        root[i] = prv;
        for(auto &j : cur_insec[i]){
            int s = a[j.i1].x;
            int e = a[j.i2].x;
            query(s, e, 1, 100000, root[i], ~j.cmp);
        }
    }
}
 
vector<edg> edges;
 
void dfs(int x, int p, int q){
    if(vis[x]) return;
    vis[x] = 1;
    for(auto &i : gph[x]){
        if(i != p){
            edges.push_back({i, x, q});
            dfs(i, x, ~q);
            break;
        }
    }
}
 
int main(){
    scanf("%d",&n);
    for(int i=0; i<n; i++){
        scanf("%d %d",&a[i].x,&a[i].y);
        a[i].idx = i;
    }
    if(n % 2 == 1){
        puts("NE");
        return 0;
    }
    sort(a, a + n, [&](const point &a, const point &b){
        return pi(a.x, a.y) < pi(b.x, b.y);
    });
    for(int i=1; i<n; i++){
        if(a[i-1].x == a[i].x){
            gph[a[i-1].idx].push_back(a[i].idx);
            gph[a[i].idx].push_back(a[i-1].idx);
        }
    }
    sort(a, a + n, [&](const point &a, const point &b){
        return pi(a.y, a.x) < pi(b.y, b.x);
    });
    for(int i=1; i<n; i++){
        if(a[i-1].y == a[i].y){
            gph[a[i-1].idx].push_back(a[i].idx);
            gph[a[i].idx].push_back(a[i-1].idx);
        }
    }
    sort(a, a + n, [&](const point &a, const point &b){
        return a.idx < b.idx;
    });
    twosat.init(2040000);
    for(int i=0; i<n; i++){
        if(vis[i]) continue;
        if(sz(gph[i]) == 0){
            puts("NE");
            return 0;
        }
        if(sz(gph[i]) == 1){
            int cur_edge = sz(edges);
            dfs(i, -1, cmp);
            int diff_edge = sz(edges) - cur_edge;
            if(diff_edge % 2){
                twosat.add_edge(~cmp, cmp);
            }
            cmp++;
        }
    }
    for(int i=0; i<n; i++){
        if(vis[i]) continue;
        if(sz(gph[i]) == 2){
        	if(pi(a[gph[i][0]].x, a[gph[i][0]].y) == pi(a[i].x, a[i].y)){
        		edges.push_back({i, gph[i][0], cmp});
        		cmp++;
			}
            dfs(i, -1, cmp);
            cmp++;
        }
    }
    vector<edg> vert, hori;
    for(auto &i : edges){
        if(a[i.i1].x == a[i.i2].x) vert.push_back(i);
        else hori.push_back(i);
    }
    for(auto &i : vert) if(a[i.i1].y > a[i.i2].y) swap(i.i1, i.i2);
    for(auto &i : hori) if(a[i.i1].x > a[i.i2].x) swap(i.i1, i.i2);
    Do(vert, hori);
    vector<int> ans; ans.resize(2040000);
    if(!twosat.satisfy(ans)){
        puts("NE");
        return 0;
    }
    puts("DA");
    for(auto &i : edges){
        if(i.cmp < 0 && !ans[~i.cmp]) printf("%d %d\n", i.i1 + 1, i.i2 + 1);
        if(i.cmp >= 0 && ans[i.cmp]) printf("%d %d\n", i.i1 + 1, i.i2 + 1);
    }
}

Compilation message

matching.cpp: In function 'int main()':
matching.cpp:189:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
matching.cpp:191:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&a[i].x,&a[i].y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 197 ms 156792 KB Output is correct
2 Correct 201 ms 156924 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 197 ms 156792 KB Output is correct
2 Correct 201 ms 156924 KB Output is correct
3 Correct 200 ms 156792 KB Output is correct
4 Correct 195 ms 156792 KB Output is correct
5 Correct 196 ms 157008 KB Output is correct
6 Incorrect 197 ms 156792 KB Output isn't correct
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 197 ms 156792 KB Output is correct
2 Correct 201 ms 156924 KB Output is correct
3 Correct 200 ms 156792 KB Output is correct
4 Correct 195 ms 156792 KB Output is correct
5 Correct 196 ms 157008 KB Output is correct
6 Incorrect 197 ms 156792 KB Output isn't correct
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 197 ms 156792 KB Output is correct
2 Correct 201 ms 156924 KB Output is correct
3 Correct 200 ms 156792 KB Output is correct
4 Correct 195 ms 156792 KB Output is correct
5 Correct 196 ms 157008 KB Output is correct
6 Incorrect 197 ms 156792 KB Output isn't correct
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 197 ms 156792 KB Output is correct
2 Correct 201 ms 156924 KB Output is correct
3 Correct 200 ms 156792 KB Output is correct
4 Correct 195 ms 156792 KB Output is correct
5 Correct 196 ms 157008 KB Output is correct
6 Incorrect 197 ms 156792 KB Output isn't correct
7 Halted 0 ms 0 KB -