답안 #1022696

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1022696	2024-07-14T01:45:13 Z	boyliguanhan	낙하산 고리들 (IOI12_rings)	C++17	100 / 100	768 ms	138868 KB

rings

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #1022696

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 17.0 / 17.0

Subtask #3 18.0 / 18.0

Subtask #4 14.0 / 14.0

Subtask #5 31.0 / 31.0

Subtask #1
20.0 / 20.0

Subtask #2
17.0 / 17.0

Subtask #3
18.0 / 18.0

Subtask #4
14.0 / 14.0

Subtask #5
31.0 / 31.0