답안 #1022691

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1022691	2024-07-13T23:59:44 Z	vjudge1	낙하산 고리들 (IOI12_rings)	C++17	100 / 100	724 ms	139180 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	35 ms	82512 KB	Output is correct
2	Correct	36 ms	82512 KB	Output is correct
3	Correct	36 ms	82524 KB	Output is correct
4	Correct	35 ms	82520 KB	Output is correct
5	Correct	35 ms	82660 KB	Output is correct
6	Correct	36 ms	82824 KB	Output is correct
7	Correct	35 ms	82524 KB	Output is correct
8	Correct	36 ms	82524 KB	Output is correct
9	Correct	36 ms	82512 KB	Output is correct
10	Correct	41 ms	82548 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	256 ms	111780 KB	Output is correct
2	Correct	465 ms	112308 KB	Output is correct
3	Correct	676 ms	99412 KB	Output is correct
4	Correct	622 ms	138672 KB	Output is correct
5	Correct	633 ms	139180 KB	Output is correct
6	Correct	656 ms	137384 KB	Output is correct
7	Correct	611 ms	99452 KB	Output is correct
8	Correct	636 ms	129936 KB	Output is correct
9	Correct	724 ms	136620 KB	Output is correct
10	Correct	440 ms	135852 KB	Output is correct

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	82512 KB	Output is correct
2	Correct	36 ms	82512 KB	Output is correct
3	Correct	36 ms	82524 KB	Output is correct
4	Correct	35 ms	82520 KB	Output is correct
5	Correct	35 ms	82660 KB	Output is correct
6	Correct	36 ms	82824 KB	Output is correct
7	Correct	35 ms	82524 KB	Output is correct
8	Correct	36 ms	82524 KB	Output is correct
9	Correct	36 ms	82512 KB	Output is correct
10	Correct	41 ms	82548 KB	Output is correct
11	Correct	35 ms	82516 KB	Output is correct
12	Correct	37 ms	83036 KB	Output is correct
13	Correct	37 ms	82772 KB	Output is correct
14	Correct	36 ms	82512 KB	Output is correct
15	Correct	36 ms	82524 KB	Output is correct
16	Correct	37 ms	83028 KB	Output is correct
17	Correct	37 ms	82524 KB	Output is correct
18	Correct	37 ms	82632 KB	Output is correct
19	Correct	36 ms	83008 KB	Output is correct
20	Correct	47 ms	82772 KB	Output is correct

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	82512 KB	Output is correct
2	Correct	36 ms	82512 KB	Output is correct
3	Correct	36 ms	82524 KB	Output is correct
4	Correct	35 ms	82520 KB	Output is correct
5	Correct	35 ms	82660 KB	Output is correct
6	Correct	36 ms	82824 KB	Output is correct
7	Correct	35 ms	82524 KB	Output is correct
8	Correct	36 ms	82524 KB	Output is correct
9	Correct	36 ms	82512 KB	Output is correct
10	Correct	41 ms	82548 KB	Output is correct
11	Correct	35 ms	82516 KB	Output is correct
12	Correct	37 ms	83036 KB	Output is correct
13	Correct	37 ms	82772 KB	Output is correct
14	Correct	36 ms	82512 KB	Output is correct
15	Correct	36 ms	82524 KB	Output is correct
16	Correct	37 ms	83028 KB	Output is correct
17	Correct	37 ms	82524 KB	Output is correct
18	Correct	37 ms	82632 KB	Output is correct
19	Correct	36 ms	83008 KB	Output is correct
20	Correct	47 ms	82772 KB	Output is correct
21	Correct	44 ms	84300 KB	Output is correct
22	Correct	51 ms	85208 KB	Output is correct
23	Correct	60 ms	86132 KB	Output is correct
24	Correct	59 ms	83500 KB	Output is correct
25	Correct	43 ms	82916 KB	Output is correct
26	Correct	58 ms	83792 KB	Output is correct
27	Correct	77 ms	87236 KB	Output is correct
28	Correct	61 ms	84048 KB	Output is correct
29	Correct	53 ms	83840 KB	Output is correct
30	Correct	81 ms	87784 KB	Output is correct

Subtask #5
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	82512 KB	Output is correct
2	Correct	36 ms	82512 KB	Output is correct
3	Correct	36 ms	82524 KB	Output is correct
4	Correct	35 ms	82520 KB	Output is correct
5	Correct	35 ms	82660 KB	Output is correct
6	Correct	36 ms	82824 KB	Output is correct
7	Correct	35 ms	82524 KB	Output is correct
8	Correct	36 ms	82524 KB	Output is correct
9	Correct	36 ms	82512 KB	Output is correct
10	Correct	41 ms	82548 KB	Output is correct
11	Correct	256 ms	111780 KB	Output is correct
12	Correct	465 ms	112308 KB	Output is correct
13	Correct	676 ms	99412 KB	Output is correct
14	Correct	622 ms	138672 KB	Output is correct
15	Correct	633 ms	139180 KB	Output is correct
16	Correct	656 ms	137384 KB	Output is correct
17	Correct	611 ms	99452 KB	Output is correct
18	Correct	636 ms	129936 KB	Output is correct
19	Correct	724 ms	136620 KB	Output is correct
20	Correct	440 ms	135852 KB	Output is correct
21	Correct	35 ms	82516 KB	Output is correct
22	Correct	37 ms	83036 KB	Output is correct
23	Correct	37 ms	82772 KB	Output is correct
24	Correct	36 ms	82512 KB	Output is correct
25	Correct	36 ms	82524 KB	Output is correct
26	Correct	37 ms	83028 KB	Output is correct
27	Correct	37 ms	82524 KB	Output is correct
28	Correct	37 ms	82632 KB	Output is correct
29	Correct	36 ms	83008 KB	Output is correct
30	Correct	47 ms	82772 KB	Output is correct
31	Correct	44 ms	84300 KB	Output is correct
32	Correct	51 ms	85208 KB	Output is correct
33	Correct	60 ms	86132 KB	Output is correct
34	Correct	59 ms	83500 KB	Output is correct
35	Correct	43 ms	82916 KB	Output is correct
36	Correct	58 ms	83792 KB	Output is correct
37	Correct	77 ms	87236 KB	Output is correct
38	Correct	61 ms	84048 KB	Output is correct
39	Correct	53 ms	83840 KB	Output is correct
40	Correct	81 ms	87784 KB	Output is correct
41	Correct	144 ms	98104 KB	Output is correct
42	Correct	302 ms	107732 KB	Output is correct
43	Correct	176 ms	87944 KB	Output is correct
44	Correct	448 ms	98388 KB	Output is correct
45	Correct	508 ms	97708 KB	Output is correct
46	Correct	414 ms	130216 KB	Output is correct
47	Correct	677 ms	130984 KB	Output is correct
48	Correct	299 ms	94980 KB	Output is correct
49	Correct	395 ms	127916 KB	Output is correct
50	Correct	417 ms	127516 KB	Output is correct
51	Correct	186 ms	90192 KB	Output is correct
52	Correct	376 ms	96304 KB	Output is correct
53	Correct	268 ms	93856 KB	Output is correct
54	Correct	518 ms	119664 KB	Output is correct
55	Correct	501 ms	98700 KB	Output is correct

답안 #1022691

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