oj.uz

답안 #699210

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
699210 2023-02-16T06:09:30 Z Cross_Ratio 낙하산 고리들 (IOI12_rings) C++14
52 / 100
 4000 ms 152936 KB 
#include <bits/stdc++.h>
using namespace std;
set<array<int, 2>> S2;
vector<vector<int>> adj;
struct UnionFind {
    vector<int> root;
    int cypt = -1;
    bool deg3 = false;
    int pt = -1;
    void init(int N) {
        root.resize(N);
        fill(root.begin(),root.end(),-1);
    }
    void bye() {
        root.clear();
        root.shrink_to_fit();
    }
    int Find(int n) {
        if(root[n]<0) return n;
        int r = Find(root[n]);
        root[n] = r;
        return r;
    }
    void Merge(int x, int y) {
        if(deg3) return;
        if(pt!=-1&&cypt!=-1) return;
        if(cypt==-2) return;
        int d1 = adj[x].size() - (S2.find({min(pt, x), max(pt, x)})!=S2.end()?1:0);
        int d2 = adj[y].size() - (S2.find({min(pt, y), max(pt, y)})!=S2.end()?1:0);
        if(d1>=3) deg3 = true;
        if(d2>=3) deg3 = true;
        if(deg3) bye();
        if(deg3) return;
        x = Find(x), y = Find(y);
        if(x==y) {
            if(cypt==-1) cypt = x;
            else cypt = -2;
            if(cypt!=-1&&pt!=-1) bye();
            return;
        }
        if(root[x]>root[y]) swap(x, y);
        root[x] += root[y];
        root[y] = x;
    }
};
int N;
int cnt;
set<int> S;
UnionFind U;
UnionFind UF[4];
map<int, int> id;
int id2[5];
bool idcnt = false;
void Init(int _N) {
    N = _N;
    adj.resize(N);
    int i;
    for(i=0;i<N;i++) S.insert(i);
    if(S.size() <= 4 && !idcnt) {
        idcnt = true;
        int ck = 0;
        for(int n : S) {
            id[n] = ck;
            UF[ck].pt = n;
            id2[ck] = n;
            ck++;
            UF[ck].init(N);
        }
    }
    else U.init(N);
}
void Link(int x, int y) {
    adj[x].push_back(y);
    adj[y].push_back(x);
    S2.insert({min(x, y), max(x, y)});
    if(adj[x].size() == 3) {
        set<int> S2;
        S2.insert(x);
        for(int n : adj[x]) S2.insert(n);
        vector<int> v;
        for(int n : S) {
            if(S2.find(n) == S2.end()) v.push_back(n);
        }
        for(int n : v) S.erase(n);
    }
    if(adj[x].size() >= 4) {
        if(S.find(x) == S.end()) S = set<int> {};
        else S = set<int>{x};
    }
    if(adj[y].size() == 3) {
        set<int> S2;
        S2.insert(y);
        for(int n : adj[y]) S2.insert(n);
        vector<int> v;
        for(int n : S) {
            if(S2.find(n) == S2.end()) v.push_back(n);
        }
        for(int n : v) S.erase(n);
    }
    if(adj[y].size() >= 4) {
        if(S.find(y) == S.end()) S = set<int> {};
        else S = set<int>{y};
    }
    bool now = false;
    if(S.size() <= 4 && !idcnt) {
        idcnt = true;
        now = true;
        int ck = 0;
        U.bye();
        for(int n : S) {
            id[n] = ck;
            id2[ck] = n;
            UF[ck].pt = n;
            UF[ck].init(N);
            for(auto k : S2) {
                if(k[0] != n && k[1] != n) {
                    UF[ck].Merge(k[0], k[1]);
                }
            }
            ck++;
        }
    }
    if(!idcnt) U.Merge(x, y);
    if(idcnt && !now) {
        for(int s : S) {
            if(x != s && y != s) {
                UF[id[s]].Merge(x, y);
            }
        }
    }
}
int CountCritical() {
    if(S.size() == 0) return 0;
    if(!idcnt) {
        //assert(!U.deg3);
        if(U.cypt==-1) return N;
        else if(U.cypt==-2) return 0;
        else return -U.root[U.Find(U.cypt)];
    }
    else {
        int cnt = 0;
        for(int n : S) {
            if(!UF[id[n]].deg3 && UF[id[n]].cypt == -1) cnt++;
        }
        return cnt;
    }
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 6 ms 724 KB Output is correct
3 Correct 5 ms 852 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 5 ms 1104 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 7 ms 980 KB Output is correct
10 Correct 7 ms 1044 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 997 ms 79572 KB Output is correct
2 Correct 2626 ms 94040 KB Output is correct
3 Correct 2107 ms 111008 KB Output is correct
4 Correct 2459 ms 152840 KB Output is correct
5 Correct 2335 ms 152936 KB Output is correct
6 Correct 2396 ms 150016 KB Output is correct
7 Correct 2117 ms 108672 KB Output is correct
8 Correct 3795 ms 130564 KB Output is correct
9 Execution timed out 4078 ms 148084 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 6 ms 724 KB Output is correct
3 Correct 5 ms 852 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 5 ms 1104 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 7 ms 980 KB Output is correct
10 Correct 7 ms 1044 KB Output is correct
11 Correct 7 ms 852 KB Output is correct
12 Correct 19 ms 1840 KB Output is correct
13 Correct 16 ms 1668 KB Output is correct
14 Correct 9 ms 1236 KB Output is correct
15 Correct 13 ms 2004 KB Output is correct
16 Correct 8 ms 1876 KB Output is correct
17 Correct 8 ms 1364 KB Output is correct
18 Correct 11 ms 2132 KB Output is correct
19 Correct 9 ms 1848 KB Output is correct
20 Correct 19 ms 1620 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 6 ms 724 KB Output is correct
3 Correct 5 ms 852 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 5 ms 1104 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 7 ms 980 KB Output is correct
10 Correct 7 ms 1044 KB Output is correct
11 Correct 7 ms 852 KB Output is correct
12 Correct 19 ms 1840 KB Output is correct
13 Correct 16 ms 1668 KB Output is correct
14 Correct 9 ms 1236 KB Output is correct
15 Correct 13 ms 2004 KB Output is correct
16 Correct 8 ms 1876 KB Output is correct
17 Correct 8 ms 1364 KB Output is correct
18 Correct 11 ms 2132 KB Output is correct
19 Correct 9 ms 1848 KB Output is correct
20 Correct 19 ms 1620 KB Output is correct
21 Correct 36 ms 6236 KB Output is correct
22 Correct 61 ms 9712 KB Output is correct
23 Correct 75 ms 12236 KB Output is correct
24 Correct 96 ms 8044 KB Output is correct
25 Correct 41 ms 8368 KB Output is correct
26 Correct 94 ms 9176 KB Output is correct
27 Correct 97 ms 13132 KB Output is correct
28 Correct 92 ms 9216 KB Output is correct
29 Correct 66 ms 8596 KB Output is correct
30 Correct 119 ms 15304 KB Output is correct

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 6 ms 724 KB Output is correct
3 Correct 5 ms 852 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 5 ms 1104 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 7 ms 980 KB Output is correct
10 Correct 7 ms 1044 KB Output is correct
11 Correct 997 ms 79572 KB Output is correct
12 Correct 2626 ms 94040 KB Output is correct
13 Correct 2107 ms 111008 KB Output is correct
14 Correct 2459 ms 152840 KB Output is correct
15 Correct 2335 ms 152936 KB Output is correct
16 Correct 2396 ms 150016 KB Output is correct
17 Correct 2117 ms 108672 KB Output is correct
18 Correct 3795 ms 130564 KB Output is correct
19 Execution timed out 4078 ms 148084 KB Time limit exceeded
20 Halted 0 ms 0 KB -