oj.uz

답안 #658126

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
658126 2022-11-12T08:23:32 Z jiahng 낙하산 고리들 (IOI12_rings) C++14
69 / 100
 4000 ms 163476 KB 
#include <bits/stdc++.h>
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
 
typedef long long ll;
#define ll int
typedef pair<int,int> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 1000010
#define INF (ll)1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
int N;
int d[maxn], maxD;
vi st[maxn], adj[maxn],cycles[5];
vpi all_edges;
int p[maxn][5], edges[maxn][5], sz[maxn][5], ncycles[5];
vpi pos;
int fl(int i, int x){
    if (p[x][i] == x) return x;
    return p[x][i] = fl(i, p[x][i]);
}
 
void add(int i, int A, int B){
    if (sz[fl(i,A)][i] > sz[fl(i,B)][i]) swap(A,B);
    
    if (fl(i, A) != fl(i,B)){
        int pA = fl(i,A), pB = fl(i,B);
        if (edges[pA][i] >= sz[pA][i]) ncycles[i]--;
        if (edges[pB][i] >= sz[pB][i]) ncycles[i]--;
        sz[pB][i] += sz[pA][i];
        edges[pB][i] += edges[pA][i];
        p[pA][i] = pB;
    }else if (edges[fl(i,A)][i] >= sz[fl(i,A)][i]) ncycles[i]--;
    edges[fl(i,B)][i]++;
    if (edges[fl(i,B)][i] >= sz[fl(i,B)][i]){
        ncycles[i]++; cycles[i].pb(fl(i,B));
    }
}
int bigx;
int gt3 = 0;

void Init(int N_) {
    N = N_;
    maxD = 0;
    FOR(i,0,4) FOR(j,0,N-1) p[j][i] = j,sz[j][i] = 1;
    bigx = -1;
}
void Link(int A, int B) {
    if (d[A] == 3) gt3++;
    if (d[B] == 3) gt3++;
    d[A]++; d[B]++;
    st[d[A]].pb(A); st[d[B]].pb(B);
 
    adj[A].pb(B); adj[B].pb(A);
 
    if (pos.empty() && (d[A] == 3 || d[B] == 3)){
        if (d[A] == 3){
            aFOR(i, adj[A]) pos.pb(pi(i,pos.size()));
            pos.pb(pi(A, pos.size()));
        }else if (d[B] == 3){
            pos.pb(pi(B, pos.size())); aFOR(i, adj[B]) pos.pb(pi(i,pos.size()));
        }
        FOR(i,0,pos.size()-1){
            aFOR(j, all_edges) if (j.f != pos[i].f && j.s != pos[i].f) add(pos[i].s,j.f,j.s);
        }
    }
    all_edges.pb(pi(A,B));
    maxD = max({maxD, d[A], d[B]});
 
    add(4,A,B);
    FOR(i,0,(int)pos.size()-1) if (A != pos[i].f && B != pos[i].f) add(pos[i].s,A,B);
}
 
int CountCritical() {
    if (N == 1) return 1;
    if (maxD >= 4){
        if (gt3 > 1) return 0;
        if (st[maxD].size() == 1){
            int x = st[maxD][0];
            int idx = -1;
            aFOR(i, pos) if (i.f == x) idx = i.s;
            if (idx == -1 || !cycles[idx].empty()) return 0;
            aFOR(i, st[3]) if (i != x && find(all(adj[i]), x) == adj[i].end()) return 0;
            return 1;
        }else return 0;
    }else if (maxD <= 1) return N;
    else if (maxD == 3){
        if (st[3].size() > 4) return 0;
       
        int ans = 0;
        vpi npos;
        FOR(i,0,pos.size()-1){
            bool no = 0;
            aFOR(j, st[3]) if (pos[i].f != j && find(all(adj[j]), pos[i].f) == adj[j].end()){
                no = 1; break;
            }
            npos.pb(pos[i]);
            if (no) continue;
            if (cycles[i].empty()){
                ans++;
            }
        }
        pos.swap(npos);
        return ans;
    }else{
        if (ncycles[4] == 0) return N;
        else if (ncycles[4] == 1) return sz[fl(4,cycles[4][0])][4];
        else return 0;
    }
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 26 ms 47736 KB Output is correct
3 Correct 25 ms 47828 KB Output is correct
4 Correct 24 ms 47388 KB Output is correct
5 Correct 28 ms 47620 KB Output is correct
6 Correct 29 ms 47824 KB Output is correct
7 Correct 24 ms 47572 KB Output is correct
8 Correct 25 ms 47688 KB Output is correct
9 Correct 25 ms 47828 KB Output is correct
10 Correct 26 ms 47840 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 565 ms 99704 KB Output is correct
2 Correct 1319 ms 136028 KB Output is correct
3 Correct 1363 ms 163476 KB Output is correct
4 Correct 1330 ms 156680 KB Output is correct
5 Correct 1350 ms 156768 KB Output is correct
6 Correct 1299 ms 154876 KB Output is correct
7 Correct 1297 ms 162428 KB Output is correct
8 Correct 1783 ms 149956 KB Output is correct
9 Correct 2045 ms 156852 KB Output is correct
10 Correct 958 ms 134624 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 26 ms 47736 KB Output is correct
3 Correct 25 ms 47828 KB Output is correct
4 Correct 24 ms 47388 KB Output is correct
5 Correct 28 ms 47620 KB Output is correct
6 Correct 29 ms 47824 KB Output is correct
7 Correct 24 ms 47572 KB Output is correct
8 Correct 25 ms 47688 KB Output is correct
9 Correct 25 ms 47828 KB Output is correct
10 Correct 26 ms 47840 KB Output is correct
11 Correct 27 ms 47844 KB Output is correct
12 Correct 32 ms 48404 KB Output is correct
13 Correct 30 ms 48348 KB Output is correct
14 Correct 29 ms 48320 KB Output is correct
15 Correct 29 ms 48968 KB Output is correct
16 Correct 30 ms 48320 KB Output is correct
17 Correct 28 ms 48716 KB Output is correct
18 Correct 33 ms 49084 KB Output is correct
19 Correct 28 ms 48540 KB Output is correct
20 Correct 29 ms 48460 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 26 ms 47736 KB Output is correct
3 Correct 25 ms 47828 KB Output is correct
4 Correct 24 ms 47388 KB Output is correct
5 Correct 28 ms 47620 KB Output is correct
6 Correct 29 ms 47824 KB Output is correct
7 Correct 24 ms 47572 KB Output is correct
8 Correct 25 ms 47688 KB Output is correct
9 Correct 25 ms 47828 KB Output is correct
10 Correct 26 ms 47840 KB Output is correct
11 Correct 27 ms 47844 KB Output is correct
12 Correct 32 ms 48404 KB Output is correct
13 Correct 30 ms 48348 KB Output is correct
14 Correct 29 ms 48320 KB Output is correct
15 Correct 29 ms 48968 KB Output is correct
16 Correct 30 ms 48320 KB Output is correct
17 Correct 28 ms 48716 KB Output is correct
18 Correct 33 ms 49084 KB Output is correct
19 Correct 28 ms 48540 KB Output is correct
20 Correct 29 ms 48460 KB Output is correct
21 Correct 54 ms 51380 KB Output is correct
22 Correct 59 ms 54256 KB Output is correct
23 Correct 76 ms 56456 KB Output is correct
24 Correct 2080 ms 56608 KB Output is correct
25 Correct 533 ms 54112 KB Output is correct
26 Correct 84 ms 55176 KB Output is correct
27 Correct 81 ms 56100 KB Output is correct
28 Correct 110 ms 57704 KB Output is correct
29 Correct 64 ms 55640 KB Output is correct
30 Correct 114 ms 58220 KB Output is correct

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 26 ms 47736 KB Output is correct
3 Correct 25 ms 47828 KB Output is correct
4 Correct 24 ms 47388 KB Output is correct
5 Correct 28 ms 47620 KB Output is correct
6 Correct 29 ms 47824 KB Output is correct
7 Correct 24 ms 47572 KB Output is correct
8 Correct 25 ms 47688 KB Output is correct
9 Correct 25 ms 47828 KB Output is correct
10 Correct 26 ms 47840 KB Output is correct
11 Correct 565 ms 99704 KB Output is correct
12 Correct 1319 ms 136028 KB Output is correct
13 Correct 1363 ms 163476 KB Output is correct
14 Correct 1330 ms 156680 KB Output is correct
15 Correct 1350 ms 156768 KB Output is correct
16 Correct 1299 ms 154876 KB Output is correct
17 Correct 1297 ms 162428 KB Output is correct
18 Correct 1783 ms 149956 KB Output is correct
19 Correct 2045 ms 156852 KB Output is correct
20 Correct 958 ms 134624 KB Output is correct
21 Correct 27 ms 47844 KB Output is correct
22 Correct 32 ms 48404 KB Output is correct
23 Correct 30 ms 48348 KB Output is correct
24 Correct 29 ms 48320 KB Output is correct
25 Correct 29 ms 48968 KB Output is correct
26 Correct 30 ms 48320 KB Output is correct
27 Correct 28 ms 48716 KB Output is correct
28 Correct 33 ms 49084 KB Output is correct
29 Correct 28 ms 48540 KB Output is correct
30 Correct 29 ms 48460 KB Output is correct
31 Correct 54 ms 51380 KB Output is correct
32 Correct 59 ms 54256 KB Output is correct
33 Correct 76 ms 56456 KB Output is correct
34 Correct 2080 ms 56608 KB Output is correct
35 Correct 533 ms 54112 KB Output is correct
36 Correct 84 ms 55176 KB Output is correct
37 Correct 81 ms 56100 KB Output is correct
38 Correct 110 ms 57704 KB Output is correct
39 Correct 64 ms 55640 KB Output is correct
40 Correct 114 ms 58220 KB Output is correct
41 Correct 277 ms 88376 KB Output is correct
42 Correct 802 ms 114316 KB Output is correct
43 Execution timed out 4053 ms 109016 KB Time limit exceeded
44 Halted 0 ms 0 KB -