oj.uz

Submission #658110

# Submission time Handle Problem Language Result Execution time Memory
658110 2022-11-12T07:44:45 Z jiahng Parachute rings (IOI12_rings) C++14
69 / 100
 4000 ms 168620 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];
unordered_set <int,custom_hash> cycles[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);
    edges[i][fl(i,B)]++;
    if (fl(i, A) != fl(i,B)){
        int pA = fl(i,A), pB = fl(i,B);
        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;
    }
    if (edges[i][fl(i,B)] >= sz[i][fl(i,B)]) cycles[i].insert(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 (cycles[5].size() == 0) return N;
        else if (cycles[5].size() == 1) return sz[5][fl(5,*cycles[5].begin())];
        else return 0;
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47316 KB Output is correct
2 Correct 23 ms 47936 KB Output is correct
3 Correct 26 ms 48024 KB Output is correct
4 Correct 23 ms 47560 KB Output is correct
5 Correct 25 ms 47764 KB Output is correct
6 Correct 26 ms 48056 KB Output is correct
7 Correct 22 ms 47844 KB Output is correct
8 Correct 25 ms 47852 KB Output is correct
9 Correct 24 ms 48020 KB Output is correct
10 Correct 25 ms 48100 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 110512 KB Output is correct
2 Correct 1969 ms 145644 KB Output is correct
3 Correct 2520 ms 165912 KB Output is correct
4 Correct 1263 ms 168440 KB Output is correct
5 Correct 1265 ms 168620 KB Output is correct
6 Correct 1291 ms 166636 KB Output is correct
7 Correct 2418 ms 165464 KB Output is correct
8 Correct 1931 ms 161008 KB Output is correct
9 Correct 2048 ms 168432 KB Output is correct
10 Correct 972 ms 165964 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47316 KB Output is correct
2 Correct 23 ms 47936 KB Output is correct
3 Correct 26 ms 48024 KB Output is correct
4 Correct 23 ms 47560 KB Output is correct
5 Correct 25 ms 47764 KB Output is correct
6 Correct 26 ms 48056 KB Output is correct
7 Correct 22 ms 47844 KB Output is correct
8 Correct 25 ms 47852 KB Output is correct
9 Correct 24 ms 48020 KB Output is correct
10 Correct 25 ms 48100 KB Output is correct
11 Correct 26 ms 48060 KB Output is correct
12 Correct 29 ms 48732 KB Output is correct
13 Correct 33 ms 48664 KB Output is correct
14 Correct 28 ms 48468 KB Output is correct
15 Correct 29 ms 49384 KB Output is correct
16 Correct 31 ms 48724 KB Output is correct
17 Correct 30 ms 48724 KB Output is correct
18 Correct 29 ms 49492 KB Output is correct
19 Correct 28 ms 48736 KB Output is correct
20 Correct 29 ms 48784 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47316 KB Output is correct
2 Correct 23 ms 47936 KB Output is correct
3 Correct 26 ms 48024 KB Output is correct
4 Correct 23 ms 47560 KB Output is correct
5 Correct 25 ms 47764 KB Output is correct
6 Correct 26 ms 48056 KB Output is correct
7 Correct 22 ms 47844 KB Output is correct
8 Correct 25 ms 47852 KB Output is correct
9 Correct 24 ms 48020 KB Output is correct
10 Correct 25 ms 48100 KB Output is correct
11 Correct 26 ms 48060 KB Output is correct
12 Correct 29 ms 48732 KB Output is correct
13 Correct 33 ms 48664 KB Output is correct
14 Correct 28 ms 48468 KB Output is correct
15 Correct 29 ms 49384 KB Output is correct
16 Correct 31 ms 48724 KB Output is correct
17 Correct 30 ms 48724 KB Output is correct
18 Correct 29 ms 49492 KB Output is correct
19 Correct 28 ms 48736 KB Output is correct
20 Correct 29 ms 48784 KB Output is correct
21 Correct 41 ms 52552 KB Output is correct
22 Correct 55 ms 55588 KB Output is correct
23 Correct 69 ms 57808 KB Output is correct
24 Correct 2115 ms 57080 KB Output is correct
25 Correct 525 ms 55372 KB Output is correct
26 Correct 109 ms 57664 KB Output is correct
27 Correct 69 ms 57716 KB Output is correct
28 Correct 143 ms 58092 KB Output is correct
29 Correct 77 ms 56940 KB Output is correct
30 Correct 78 ms 59448 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47316 KB Output is correct
2 Correct 23 ms 47936 KB Output is correct
3 Correct 26 ms 48024 KB Output is correct
4 Correct 23 ms 47560 KB Output is correct
5 Correct 25 ms 47764 KB Output is correct
6 Correct 26 ms 48056 KB Output is correct
7 Correct 22 ms 47844 KB Output is correct
8 Correct 25 ms 47852 KB Output is correct
9 Correct 24 ms 48020 KB Output is correct
10 Correct 25 ms 48100 KB Output is correct
11 Correct 503 ms 110512 KB Output is correct
12 Correct 1969 ms 145644 KB Output is correct
13 Correct 2520 ms 165912 KB Output is correct
14 Correct 1263 ms 168440 KB Output is correct
15 Correct 1265 ms 168620 KB Output is correct
16 Correct 1291 ms 166636 KB Output is correct
17 Correct 2418 ms 165464 KB Output is correct
18 Correct 1931 ms 161008 KB Output is correct
19 Correct 2048 ms 168432 KB Output is correct
20 Correct 972 ms 165964 KB Output is correct
21 Correct 26 ms 48060 KB Output is correct
22 Correct 29 ms 48732 KB Output is correct
23 Correct 33 ms 48664 KB Output is correct
24 Correct 28 ms 48468 KB Output is correct
25 Correct 29 ms 49384 KB Output is correct
26 Correct 31 ms 48724 KB Output is correct
27 Correct 30 ms 48724 KB Output is correct
28 Correct 29 ms 49492 KB Output is correct
29 Correct 28 ms 48736 KB Output is correct
30 Correct 29 ms 48784 KB Output is correct
31 Correct 41 ms 52552 KB Output is correct
32 Correct 55 ms 55588 KB Output is correct
33 Correct 69 ms 57808 KB Output is correct
34 Correct 2115 ms 57080 KB Output is correct
35 Correct 525 ms 55372 KB Output is correct
36 Correct 109 ms 57664 KB Output is correct
37 Correct 69 ms 57716 KB Output is correct
38 Correct 143 ms 58092 KB Output is correct
39 Correct 77 ms 56940 KB Output is correct
40 Correct 78 ms 59448 KB Output is correct
41 Correct 243 ms 96212 KB Output is correct
42 Correct 731 ms 132384 KB Output is correct
43 Execution timed out 4029 ms 120012 KB Time limit exceeded
44 Halted 0 ms 0 KB -