oj.uz

Submission #658113

# Submission time Handle Problem Language Result Execution time Memory
658113 2022-11-12T07:51:58 Z jiahng Parachute rings (IOI12_rings) C++14
69 / 100
 4000 ms 176080 KB 
#include <bits/stdc++.h>
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;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
vi st[maxn];
int d[maxn];
int maxD;
vi adj[maxn];
 
vpi all_edges;
int p[6][maxn];
int edges[6][maxn], sz[6][maxn];
vi cycles[6];
int 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;
    FOR(i,0,N-1){
        adj[i].clear(); st[i].clear();
    }
    FOR(i,0,5) cycles[i].clear();
    FOR(i,0,N-1) d[i] = 0;
    //FOR(i,0,N-1) st[0].insert(i);
    all_edges.clear();
    
    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 21 ms 47324 KB Output is correct
2 Correct 24 ms 47964 KB Output is correct
3 Correct 25 ms 48096 KB Output is correct
4 Correct 22 ms 47444 KB Output is correct
5 Correct 24 ms 47732 KB Output is correct
6 Correct 25 ms 48112 KB Output is correct
7 Correct 24 ms 47920 KB Output is correct
8 Correct 25 ms 47832 KB Output is correct
9 Correct 26 ms 48064 KB Output is correct
10 Correct 25 ms 48072 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 110452 KB Output is correct
2 Correct 1790 ms 145640 KB Output is correct
3 Correct 2245 ms 176080 KB Output is correct
4 Correct 1235 ms 168480 KB Output is correct
5 Correct 1247 ms 168496 KB Output is correct
6 Correct 1206 ms 166528 KB Output is correct
7 Correct 2161 ms 174976 KB Output is correct
8 Correct 1778 ms 161004 KB Output is correct
9 Correct 1856 ms 168396 KB Output is correct
10 Correct 914 ms 165848 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47324 KB Output is correct
2 Correct 24 ms 47964 KB Output is correct
3 Correct 25 ms 48096 KB Output is correct
4 Correct 22 ms 47444 KB Output is correct
5 Correct 24 ms 47732 KB Output is correct
6 Correct 25 ms 48112 KB Output is correct
7 Correct 24 ms 47920 KB Output is correct
8 Correct 25 ms 47832 KB Output is correct
9 Correct 26 ms 48064 KB Output is correct
10 Correct 25 ms 48072 KB Output is correct
11 Correct 27 ms 48084 KB Output is correct
12 Correct 27 ms 48724 KB Output is correct
13 Correct 27 ms 48724 KB Output is correct
14 Correct 31 ms 48588 KB Output is correct
15 Correct 31 ms 49364 KB Output is correct
16 Correct 30 ms 48680 KB Output is correct
17 Correct 28 ms 48940 KB Output is correct
18 Correct 30 ms 49492 KB Output is correct
19 Correct 31 ms 48724 KB Output is correct
20 Correct 27 ms 48780 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47324 KB Output is correct
2 Correct 24 ms 47964 KB Output is correct
3 Correct 25 ms 48096 KB Output is correct
4 Correct 22 ms 47444 KB Output is correct
5 Correct 24 ms 47732 KB Output is correct
6 Correct 25 ms 48112 KB Output is correct
7 Correct 24 ms 47920 KB Output is correct
8 Correct 25 ms 47832 KB Output is correct
9 Correct 26 ms 48064 KB Output is correct
10 Correct 25 ms 48072 KB Output is correct
11 Correct 27 ms 48084 KB Output is correct
12 Correct 27 ms 48724 KB Output is correct
13 Correct 27 ms 48724 KB Output is correct
14 Correct 31 ms 48588 KB Output is correct
15 Correct 31 ms 49364 KB Output is correct
16 Correct 30 ms 48680 KB Output is correct
17 Correct 28 ms 48940 KB Output is correct
18 Correct 30 ms 49492 KB Output is correct
19 Correct 31 ms 48724 KB Output is correct
20 Correct 27 ms 48780 KB Output is correct
21 Correct 38 ms 52580 KB Output is correct
22 Correct 51 ms 55588 KB Output is correct
23 Correct 67 ms 57704 KB Output is correct
24 Correct 2193 ms 57740 KB Output is correct
25 Correct 472 ms 55756 KB Output is correct
26 Correct 98 ms 57604 KB Output is correct
27 Correct 65 ms 57656 KB Output is correct
28 Correct 102 ms 60152 KB Output is correct
29 Correct 73 ms 56904 KB Output is correct
30 Correct 74 ms 59500 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47324 KB Output is correct
2 Correct 24 ms 47964 KB Output is correct
3 Correct 25 ms 48096 KB Output is correct
4 Correct 22 ms 47444 KB Output is correct
5 Correct 24 ms 47732 KB Output is correct
6 Correct 25 ms 48112 KB Output is correct
7 Correct 24 ms 47920 KB Output is correct
8 Correct 25 ms 47832 KB Output is correct
9 Correct 26 ms 48064 KB Output is correct
10 Correct 25 ms 48072 KB Output is correct
11 Correct 493 ms 110452 KB Output is correct
12 Correct 1790 ms 145640 KB Output is correct
13 Correct 2245 ms 176080 KB Output is correct
14 Correct 1235 ms 168480 KB Output is correct
15 Correct 1247 ms 168496 KB Output is correct
16 Correct 1206 ms 166528 KB Output is correct
17 Correct 2161 ms 174976 KB Output is correct
18 Correct 1778 ms 161004 KB Output is correct
19 Correct 1856 ms 168396 KB Output is correct
20 Correct 914 ms 165848 KB Output is correct
21 Correct 27 ms 48084 KB Output is correct
22 Correct 27 ms 48724 KB Output is correct
23 Correct 27 ms 48724 KB Output is correct
24 Correct 31 ms 48588 KB Output is correct
25 Correct 31 ms 49364 KB Output is correct
26 Correct 30 ms 48680 KB Output is correct
27 Correct 28 ms 48940 KB Output is correct
28 Correct 30 ms 49492 KB Output is correct
29 Correct 31 ms 48724 KB Output is correct
30 Correct 27 ms 48780 KB Output is correct
31 Correct 38 ms 52580 KB Output is correct
32 Correct 51 ms 55588 KB Output is correct
33 Correct 67 ms 57704 KB Output is correct
34 Correct 2193 ms 57740 KB Output is correct
35 Correct 472 ms 55756 KB Output is correct
36 Correct 98 ms 57604 KB Output is correct
37 Correct 65 ms 57656 KB Output is correct
38 Correct 102 ms 60152 KB Output is correct
39 Correct 73 ms 56904 KB Output is correct
40 Correct 74 ms 59500 KB Output is correct
41 Correct 264 ms 96268 KB Output is correct
42 Correct 710 ms 132348 KB Output is correct
43 Execution timed out 4098 ms 120048 KB Time limit exceeded
44 Halted 0 ms 0 KB -