oj.uz

Submission #1022696

# Submission time Handle Problem Language Result Execution time Memory
1022696 2024-07-14T01:45:13 Z boyliguanhan Parachute rings (IOI12_rings) C++17
100 / 100
 768 ms 138868 KB 
#define L 1<<20
#include<bits/stdc++.h>
using namespace std;
struct union_find{
    int par[L],sz[L];
    union_find(){
        memset(par,0,sizeof par);
        for(auto&i:sz)i=1;
    }
    int abp(int n){
        return par[n]?par[n]=abp(par[n]):n;
    }
    bool merge(int a,int b){
        a=abp(a);b=abp(b);
        if(a-b) par[a]=b,
            sz[b]+=sz[a];
        return a-b;
    }
} global;
struct whatthehellisthis{
    union_find a_union_find;
    int ok,deg[L];
    whatthehellisthis(){ok=1;memset(deg,0,sizeof deg);}
    void AE(int a,int b){
        ok&=a_union_find.merge(a,b);
        ok&=max(++deg[a],++deg[b])<3;
    }
} thgy[4];
int N,FAIL,deg[L];
vector<int>adj[L];
int stage2,cycsz;
int mp[L];
vector<pair<int,int>>sofar;
set<int>st;
void Init(int N_) {
    N = N_;
    cycsz=N;
}
int C;
void Link(int A, int B) {
    if(stage2){ for(auto i:st)
        if(A-i&&B-i) thgy[mp[i]].AE(A,B);
    }else {
        sofar.push_back({A,B});
        deg[A]++; deg[B]++;
        adj[A].push_back(B);
        adj[B].push_back(A);
        if(deg[A]>deg[B])
            swap(A,B);
        if(deg[B]==3){
            stage2=1;
            st.insert(B);
            for(auto i:adj[B])
                st.insert(i),mp[i]=++C;
            for(auto i:st) for(auto[x,y]:sofar)
                if(i-x&&i-y) thgy[mp[i]].AE(x,y);
        } else if(!global.merge(A,B)){
            if(cycsz-N) FAIL=1;
            else cycsz=global.sz[global.abp(A)];
        }
    }
}
int CountCritical() {
    if(FAIL)return 0;
    if(stage2){
        int ans=0;
        for(auto i:st)
            ans+=thgy[mp[i]].ok;
        return ans;
    } else return cycsz;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 82512 KB Output is correct
2 Correct 38 ms 82512 KB Output is correct
3 Correct 40 ms 82520 KB Output is correct
4 Correct 37 ms 82384 KB Output is correct
5 Correct 38 ms 82516 KB Output is correct
6 Correct 39 ms 82768 KB Output is correct
7 Correct 37 ms 82516 KB Output is correct
8 Correct 37 ms 82524 KB Output is correct
9 Correct 40 ms 82636 KB Output is correct
10 Correct 39 ms 82776 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 111796 KB Output is correct
2 Correct 513 ms 112312 KB Output is correct
3 Correct 768 ms 99608 KB Output is correct
4 Correct 652 ms 138664 KB Output is correct
5 Correct 682 ms 138868 KB Output is correct
6 Correct 647 ms 137128 KB Output is correct
7 Correct 685 ms 99152 KB Output is correct
8 Correct 735 ms 129872 KB Output is correct
9 Correct 766 ms 136628 KB Output is correct
10 Correct 453 ms 135852 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 82512 KB Output is correct
2 Correct 38 ms 82512 KB Output is correct
3 Correct 40 ms 82520 KB Output is correct
4 Correct 37 ms 82384 KB Output is correct
5 Correct 38 ms 82516 KB Output is correct
6 Correct 39 ms 82768 KB Output is correct
7 Correct 37 ms 82516 KB Output is correct
8 Correct 37 ms 82524 KB Output is correct
9 Correct 40 ms 82636 KB Output is correct
10 Correct 39 ms 82776 KB Output is correct
11 Correct 36 ms 82684 KB Output is correct
12 Correct 41 ms 83024 KB Output is correct
13 Correct 38 ms 82772 KB Output is correct
14 Correct 39 ms 82596 KB Output is correct
15 Correct 41 ms 82520 KB Output is correct
16 Correct 49 ms 83032 KB Output is correct
17 Correct 40 ms 82512 KB Output is correct
18 Correct 40 ms 82780 KB Output is correct
19 Correct 41 ms 83116 KB Output is correct
20 Correct 41 ms 82900 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 82512 KB Output is correct
2 Correct 38 ms 82512 KB Output is correct
3 Correct 40 ms 82520 KB Output is correct
4 Correct 37 ms 82384 KB Output is correct
5 Correct 38 ms 82516 KB Output is correct
6 Correct 39 ms 82768 KB Output is correct
7 Correct 37 ms 82516 KB Output is correct
8 Correct 37 ms 82524 KB Output is correct
9 Correct 40 ms 82636 KB Output is correct
10 Correct 39 ms 82776 KB Output is correct
11 Correct 36 ms 82684 KB Output is correct
12 Correct 41 ms 83024 KB Output is correct
13 Correct 38 ms 82772 KB Output is correct
14 Correct 39 ms 82596 KB Output is correct
15 Correct 41 ms 82520 KB Output is correct
16 Correct 49 ms 83032 KB Output is correct
17 Correct 40 ms 82512 KB Output is correct
18 Correct 40 ms 82780 KB Output is correct
19 Correct 41 ms 83116 KB Output is correct
20 Correct 41 ms 82900 KB Output is correct
21 Correct 49 ms 84176 KB Output is correct
22 Correct 58 ms 85200 KB Output is correct
23 Correct 76 ms 86084 KB Output is correct
24 Correct 68 ms 83280 KB Output is correct
25 Correct 45 ms 82884 KB Output is correct
26 Correct 58 ms 83792 KB Output is correct
27 Correct 65 ms 87240 KB Output is correct
28 Correct 72 ms 84048 KB Output is correct
29 Correct 59 ms 83660 KB Output is correct
30 Correct 74 ms 87748 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 82512 KB Output is correct
2 Correct 38 ms 82512 KB Output is correct
3 Correct 40 ms 82520 KB Output is correct
4 Correct 37 ms 82384 KB Output is correct
5 Correct 38 ms 82516 KB Output is correct
6 Correct 39 ms 82768 KB Output is correct
7 Correct 37 ms 82516 KB Output is correct
8 Correct 37 ms 82524 KB Output is correct
9 Correct 40 ms 82636 KB Output is correct
10 Correct 39 ms 82776 KB Output is correct
11 Correct 276 ms 111796 KB Output is correct
12 Correct 513 ms 112312 KB Output is correct
13 Correct 768 ms 99608 KB Output is correct
14 Correct 652 ms 138664 KB Output is correct
15 Correct 682 ms 138868 KB Output is correct
16 Correct 647 ms 137128 KB Output is correct
17 Correct 685 ms 99152 KB Output is correct
18 Correct 735 ms 129872 KB Output is correct
19 Correct 766 ms 136628 KB Output is correct
20 Correct 453 ms 135852 KB Output is correct
21 Correct 36 ms 82684 KB Output is correct
22 Correct 41 ms 83024 KB Output is correct
23 Correct 38 ms 82772 KB Output is correct
24 Correct 39 ms 82596 KB Output is correct
25 Correct 41 ms 82520 KB Output is correct
26 Correct 49 ms 83032 KB Output is correct
27 Correct 40 ms 82512 KB Output is correct
28 Correct 40 ms 82780 KB Output is correct
29 Correct 41 ms 83116 KB Output is correct
30 Correct 41 ms 82900 KB Output is correct
31 Correct 49 ms 84176 KB Output is correct
32 Correct 58 ms 85200 KB Output is correct
33 Correct 76 ms 86084 KB Output is correct
34 Correct 68 ms 83280 KB Output is correct
35 Correct 45 ms 82884 KB Output is correct
36 Correct 58 ms 83792 KB Output is correct
37 Correct 65 ms 87240 KB Output is correct
38 Correct 72 ms 84048 KB Output is correct
39 Correct 59 ms 83660 KB Output is correct
40 Correct 74 ms 87748 KB Output is correct
41 Correct 164 ms 98052 KB Output is correct
42 Correct 314 ms 107700 KB Output is correct
43 Correct 184 ms 87888 KB Output is correct
44 Correct 497 ms 98388 KB Output is correct
45 Correct 547 ms 97744 KB Output is correct
46 Correct 448 ms 130044 KB Output is correct
47 Correct 574 ms 131020 KB Output is correct
48 Correct 314 ms 95172 KB Output is correct
49 Correct 458 ms 127916 KB Output is correct
50 Correct 489 ms 127392 KB Output is correct
51 Correct 201 ms 90192 KB Output is correct
52 Correct 409 ms 96340 KB Output is correct
53 Correct 291 ms 93776 KB Output is correct
54 Correct 590 ms 119328 KB Output is correct
55 Correct 524 ms 98536 KB Output is correct