oj.uz

Submission #658124

# Submission time Handle Problem Language Result Execution time Memory
658124 2022-11-12T08:12:46 Z jiahng Parachute rings (IOI12_rings) C++14
69 / 100
 4000 ms 163408 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[5][maxn], edges[5][maxn], sz[5][maxn], ncycles[5];
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[i][fl(i,A)] > sz[i][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];
        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,4) FOR(j,0,N-1) p[i][j] = j,sz[i][j] = 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(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);
        }
    }
    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] && B != pos[i]) add(i,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];
            if (find(all(pos),x) == pos.end()) return 0;
            int idx = find(all(pos), x) - pos.begin();
            if (!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;
        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[4] == 0) return N;
        else if (ncycles[4] == 1) return sz[4][fl(4,cycles[4][0])];
        else return 0;
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47316 KB Output is correct
2 Correct 26 ms 47828 KB Output is correct
3 Correct 29 ms 48000 KB Output is correct
4 Correct 23 ms 47464 KB Output is correct
5 Correct 25 ms 47572 KB Output is correct
6 Correct 26 ms 47828 KB Output is correct
7 Correct 25 ms 47700 KB Output is correct
8 Correct 27 ms 47744 KB Output is correct
9 Correct 31 ms 48028 KB Output is correct
10 Correct 26 ms 47996 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 96120 KB Output is correct
2 Correct 1719 ms 136172 KB Output is correct
3 Correct 2057 ms 163408 KB Output is correct
4 Correct 1289 ms 141184 KB Output is correct
5 Correct 1258 ms 141360 KB Output is correct
6 Correct 1217 ms 139508 KB Output is correct
7 Correct 1960 ms 162364 KB Output is correct
8 Correct 1895 ms 150044 KB Output is correct
9 Correct 1998 ms 156668 KB Output is correct
10 Correct 972 ms 134676 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47316 KB Output is correct
2 Correct 26 ms 47828 KB Output is correct
3 Correct 29 ms 48000 KB Output is correct
4 Correct 23 ms 47464 KB Output is correct
5 Correct 25 ms 47572 KB Output is correct
6 Correct 26 ms 47828 KB Output is correct
7 Correct 25 ms 47700 KB Output is correct
8 Correct 27 ms 47744 KB Output is correct
9 Correct 31 ms 48028 KB Output is correct
10 Correct 26 ms 47996 KB Output is correct
11 Correct 27 ms 48016 KB Output is correct
12 Correct 29 ms 48548 KB Output is correct
13 Correct 30 ms 48596 KB Output is correct
14 Correct 28 ms 48468 KB Output is correct
15 Correct 29 ms 49100 KB Output is correct
16 Correct 28 ms 48340 KB Output is correct
17 Correct 30 ms 48808 KB Output is correct
18 Correct 32 ms 49236 KB Output is correct
19 Correct 30 ms 48384 KB Output is correct
20 Correct 30 ms 48668 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47316 KB Output is correct
2 Correct 26 ms 47828 KB Output is correct
3 Correct 29 ms 48000 KB Output is correct
4 Correct 23 ms 47464 KB Output is correct
5 Correct 25 ms 47572 KB Output is correct
6 Correct 26 ms 47828 KB Output is correct
7 Correct 25 ms 47700 KB Output is correct
8 Correct 27 ms 47744 KB Output is correct
9 Correct 31 ms 48028 KB Output is correct
10 Correct 26 ms 47996 KB Output is correct
11 Correct 27 ms 48016 KB Output is correct
12 Correct 29 ms 48548 KB Output is correct
13 Correct 30 ms 48596 KB Output is correct
14 Correct 28 ms 48468 KB Output is correct
15 Correct 29 ms 49100 KB Output is correct
16 Correct 28 ms 48340 KB Output is correct
17 Correct 30 ms 48808 KB Output is correct
18 Correct 32 ms 49236 KB Output is correct
19 Correct 30 ms 48384 KB Output is correct
20 Correct 30 ms 48668 KB Output is correct
21 Correct 40 ms 51116 KB Output is correct
22 Correct 51 ms 53288 KB Output is correct
23 Correct 59 ms 54920 KB Output is correct
24 Correct 1981 ms 56628 KB Output is correct
25 Correct 478 ms 54260 KB Output is correct
26 Correct 84 ms 54972 KB Output is correct
27 Correct 72 ms 55488 KB Output is correct
28 Correct 142 ms 58288 KB Output is correct
29 Correct 78 ms 55804 KB Output is correct
30 Correct 87 ms 56780 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47316 KB Output is correct
2 Correct 26 ms 47828 KB Output is correct
3 Correct 29 ms 48000 KB Output is correct
4 Correct 23 ms 47464 KB Output is correct
5 Correct 25 ms 47572 KB Output is correct
6 Correct 26 ms 47828 KB Output is correct
7 Correct 25 ms 47700 KB Output is correct
8 Correct 27 ms 47744 KB Output is correct
9 Correct 31 ms 48028 KB Output is correct
10 Correct 26 ms 47996 KB Output is correct
11 Correct 506 ms 96120 KB Output is correct
12 Correct 1719 ms 136172 KB Output is correct
13 Correct 2057 ms 163408 KB Output is correct
14 Correct 1289 ms 141184 KB Output is correct
15 Correct 1258 ms 141360 KB Output is correct
16 Correct 1217 ms 139508 KB Output is correct
17 Correct 1960 ms 162364 KB Output is correct
18 Correct 1895 ms 150044 KB Output is correct
19 Correct 1998 ms 156668 KB Output is correct
20 Correct 972 ms 134676 KB Output is correct
21 Correct 27 ms 48016 KB Output is correct
22 Correct 29 ms 48548 KB Output is correct
23 Correct 30 ms 48596 KB Output is correct
24 Correct 28 ms 48468 KB Output is correct
25 Correct 29 ms 49100 KB Output is correct
26 Correct 28 ms 48340 KB Output is correct
27 Correct 30 ms 48808 KB Output is correct
28 Correct 32 ms 49236 KB Output is correct
29 Correct 30 ms 48384 KB Output is correct
30 Correct 30 ms 48668 KB Output is correct
31 Correct 40 ms 51116 KB Output is correct
32 Correct 51 ms 53288 KB Output is correct
33 Correct 59 ms 54920 KB Output is correct
34 Correct 1981 ms 56628 KB Output is correct
35 Correct 478 ms 54260 KB Output is correct
36 Correct 84 ms 54972 KB Output is correct
37 Correct 72 ms 55488 KB Output is correct
38 Correct 142 ms 58288 KB Output is correct
39 Correct 78 ms 55804 KB Output is correct
40 Correct 87 ms 56780 KB Output is correct
41 Correct 264 ms 82520 KB Output is correct
42 Correct 774 ms 121996 KB Output is correct
43 Execution timed out 4049 ms 109392 KB Time limit exceeded
44 Halted 0 ms 0 KB -