oj.uz

Submission #658118

# Submission time Handle Problem Language Result Execution time Memory
658118 2022-11-12T07:58:54 Z jiahng Parachute rings (IOI12_rings) C++14
69 / 100
 4000 ms 177744 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[6];
vpi all_edges;
int p[6][maxn], edges[6][maxn], sz[6][maxn], ncycles[6];
vi pos;
int fl(int i, int x){
    if (p[i][x] == x) return x;
    return p[i][x] = fl(i, p[i][x]);
}
 
void add(int i, int A, int B){
    if (sz[fl(i,A)] > sz[fl(i,B)]) swap(A,B);
    
    if (fl(i, A) != fl(i,B)){
        int pA = fl(i,A), pB = fl(i,B);
        if (edges[i][pA] >= sz[i][pA]) ncycles[i]--;
        if (edges[i][pB] >= sz[i][pB]) ncycles[i]--;
        sz[i][pB] += sz[i][pA];
        edges[i][pB] += edges[i][pA];
        //if (cycles[i].find(pA) != cycles[i].end()) cycles[i].erase(pA);
        p[i][pA] = pB;
    }else if (edges[i][fl(i,A)] >= sz[i][fl(i,A)]) ncycles[i]--;
    edges[i][fl(i,B)]++;
    if (edges[i][fl(i,B)] >= sz[i][fl(i,B)]){
        ncycles[i]++; cycles[i].pb(fl(i,B));
    }
}
int bigx;
int gt3 = 0;

void Init(int N_) {
    N = N_;
    maxD = 0;
    FOR(i,0,5) FOR(j,0,N-1) p[i][j] = j,sz[i][j] = 1,edges[i][j]  =0;
    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(i);
            pos.pb(A);
        }else if (d[B] == 3){
            pos.pb(B); aFOR(i, adj[B]) pos.pb(i);
        }
        FOR(i,0,pos.size()-1){
            aFOR(j, all_edges) if (j.f != pos[i] && j.s != pos[i]) add(i,j.f,j.s);
        }
    }
    
    if (bigx == -1 && (d[A] >= 4 || d[B] >= 4)){
        if (d[A] >= 4) bigx = A;
        else if (d[B] >= 4) bigx = B;
        aFOR(i, all_edges) if (i.f != bigx && i.s != bigx) add(4,i.f,i.s);
    }
    
    all_edges.pb(pi(A,B));
    maxD = max({maxD, d[A], d[B]});
 
    add(5,A,B);
    FOR(i,0,(int)pos.size()-1) if (A != pos[i] && B != pos[i]) add(i,A,B);
    if (bigx != -1 && A != bigx && B != bigx) add(4, 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].begin();
            bool no = 0;
            if (!cycles[4].empty()) no = 1;
            aFOR(i, st[3]) if (i != x && find(all(adj[i]), x) == adj[i].end()){
                no = 1; break;
            }
            if (no) 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;
        FOR(i,0,pos.size()-1){
            bool no = 0;
            aFOR(j, st[3]) if (pos[i] != j && find(all(adj[j]), pos[i]) == adj[j].end()){
                no = 1; break;
            }
            if (no) continue;
            if (cycles[i].empty()){
                //cout << "! " << i << '\n';
                ans++;
            }
        }
        return ans;
    }else{
        if (ncycles[5] == 0) return N;
        else if (ncycles[5] == 1) return sz[5][fl(5,cycles[5][0])];
        else return 0;
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47444 KB Output is correct
2 Correct 25 ms 47964 KB Output is correct
3 Correct 26 ms 48100 KB Output is correct
4 Correct 23 ms 47548 KB Output is correct
5 Correct 26 ms 47776 KB Output is correct
6 Correct 25 ms 48096 KB Output is correct
7 Correct 25 ms 47776 KB Output is correct
8 Correct 28 ms 47916 KB Output is correct
9 Correct 28 ms 48128 KB Output is correct
10 Correct 33 ms 48156 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 540 ms 111960 KB Output is correct
2 Correct 1812 ms 146436 KB Output is correct
3 Correct 2295 ms 177744 KB Output is correct
4 Correct 1280 ms 169040 KB Output is correct
5 Correct 1279 ms 169244 KB Output is correct
6 Correct 1244 ms 167376 KB Output is correct
7 Correct 2171 ms 175388 KB Output is correct
8 Correct 1764 ms 161052 KB Output is correct
9 Correct 1889 ms 168560 KB Output is correct
10 Correct 897 ms 165796 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47444 KB Output is correct
2 Correct 25 ms 47964 KB Output is correct
3 Correct 26 ms 48100 KB Output is correct
4 Correct 23 ms 47548 KB Output is correct
5 Correct 26 ms 47776 KB Output is correct
6 Correct 25 ms 48096 KB Output is correct
7 Correct 25 ms 47776 KB Output is correct
8 Correct 28 ms 47916 KB Output is correct
9 Correct 28 ms 48128 KB Output is correct
10 Correct 33 ms 48156 KB Output is correct
11 Correct 27 ms 48100 KB Output is correct
12 Correct 29 ms 48724 KB Output is correct
13 Correct 30 ms 48712 KB Output is correct
14 Correct 30 ms 48564 KB Output is correct
15 Correct 30 ms 49336 KB Output is correct
16 Correct 33 ms 48724 KB Output is correct
17 Correct 30 ms 48980 KB Output is correct
18 Correct 30 ms 49504 KB Output is correct
19 Correct 28 ms 48772 KB Output is correct
20 Correct 29 ms 48724 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47444 KB Output is correct
2 Correct 25 ms 47964 KB Output is correct
3 Correct 26 ms 48100 KB Output is correct
4 Correct 23 ms 47548 KB Output is correct
5 Correct 26 ms 47776 KB Output is correct
6 Correct 25 ms 48096 KB Output is correct
7 Correct 25 ms 47776 KB Output is correct
8 Correct 28 ms 47916 KB Output is correct
9 Correct 28 ms 48128 KB Output is correct
10 Correct 33 ms 48156 KB Output is correct
11 Correct 27 ms 48100 KB Output is correct
12 Correct 29 ms 48724 KB Output is correct
13 Correct 30 ms 48712 KB Output is correct
14 Correct 30 ms 48564 KB Output is correct
15 Correct 30 ms 49336 KB Output is correct
16 Correct 33 ms 48724 KB Output is correct
17 Correct 30 ms 48980 KB Output is correct
18 Correct 30 ms 49504 KB Output is correct
19 Correct 28 ms 48772 KB Output is correct
20 Correct 29 ms 48724 KB Output is correct
21 Correct 42 ms 52616 KB Output is correct
22 Correct 52 ms 55576 KB Output is correct
23 Correct 60 ms 57800 KB Output is correct
24 Correct 1985 ms 57816 KB Output is correct
25 Correct 484 ms 55584 KB Output is correct
26 Correct 91 ms 57636 KB Output is correct
27 Correct 70 ms 57616 KB Output is correct
28 Correct 114 ms 60260 KB Output is correct
29 Correct 82 ms 56872 KB Output is correct
30 Correct 84 ms 59448 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47444 KB Output is correct
2 Correct 25 ms 47964 KB Output is correct
3 Correct 26 ms 48100 KB Output is correct
4 Correct 23 ms 47548 KB Output is correct
5 Correct 26 ms 47776 KB Output is correct
6 Correct 25 ms 48096 KB Output is correct
7 Correct 25 ms 47776 KB Output is correct
8 Correct 28 ms 47916 KB Output is correct
9 Correct 28 ms 48128 KB Output is correct
10 Correct 33 ms 48156 KB Output is correct
11 Correct 540 ms 111960 KB Output is correct
12 Correct 1812 ms 146436 KB Output is correct
13 Correct 2295 ms 177744 KB Output is correct
14 Correct 1280 ms 169040 KB Output is correct
15 Correct 1279 ms 169244 KB Output is correct
16 Correct 1244 ms 167376 KB Output is correct
17 Correct 2171 ms 175388 KB Output is correct
18 Correct 1764 ms 161052 KB Output is correct
19 Correct 1889 ms 168560 KB Output is correct
20 Correct 897 ms 165796 KB Output is correct
21 Correct 27 ms 48100 KB Output is correct
22 Correct 29 ms 48724 KB Output is correct
23 Correct 30 ms 48712 KB Output is correct
24 Correct 30 ms 48564 KB Output is correct
25 Correct 30 ms 49336 KB Output is correct
26 Correct 33 ms 48724 KB Output is correct
27 Correct 30 ms 48980 KB Output is correct
28 Correct 30 ms 49504 KB Output is correct
29 Correct 28 ms 48772 KB Output is correct
30 Correct 29 ms 48724 KB Output is correct
31 Correct 42 ms 52616 KB Output is correct
32 Correct 52 ms 55576 KB Output is correct
33 Correct 60 ms 57800 KB Output is correct
34 Correct 1985 ms 57816 KB Output is correct
35 Correct 484 ms 55584 KB Output is correct
36 Correct 91 ms 57636 KB Output is correct
37 Correct 70 ms 57616 KB Output is correct
38 Correct 114 ms 60260 KB Output is correct
39 Correct 82 ms 56872 KB Output is correct
40 Correct 84 ms 59448 KB Output is correct
41 Correct 233 ms 96336 KB Output is correct
42 Correct 706 ms 132340 KB Output is correct
43 Execution timed out 4059 ms 120084 KB Time limit exceeded
44 Halted 0 ms 0 KB -