답안 #15597 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
15597	2015-07-13T04:21:21 Z	gs14004	낙하산 고리들 (IOI12_rings)	C++14	55 / 100	4000 ms	96500 KB

rings

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
 
vector<int> graph[1000005];
int n;
 
struct disj{
    int pa[1000005];
    int degcnt[1000005][5];
    int repres3[1000005];
    int repres4[1000005];
    int cnt[1000005];
    int size[1000005];
 
    void init(int n){
        for(int i=0; i<=n; i++) pa[i] = i, degcnt[i][0] = 1, size[i] = 1, repres3[i] = repres4[i] = -1;
    }
 
    int find(int x){
        return pa[x] = (pa[x] == x ? x : find(pa[x]));
    }
 
    void uni(int p, int q){
        p = find(p); q = find(q);
        if(p == q) return;
        pa[q] = p; find(q);
        for(int i=0; i<5; i++){
            degcnt[p][i] += degcnt[q][i];
        }
        size[p] += size[q];
        repres4[p] = max(repres4[p], repres4[q]);
        repres3[p] = max(repres3[p], repres3[q]);
    }
}disj;
 
void Init(int N){
    n = N; 
    disj.init(n);
}
 
int deg[1000005];
int focus = -1;
bool deadend = 0;

void Link(int A, int B){
    graph[A].push_back(B);
    graph[B].push_back(A);
    deg[A]++, deg[B]++;
    int p = disj.find(A);
    if(deg[A] <= 4){
        disj.degcnt[p][deg[A]-1]--;
        disj.degcnt[p][deg[A]]++;
        if(deg[A] == 3) disj.repres3[p] = A;
        if(deg[A] == 4) disj.repres4[p] = A;
    }
    p = disj.find(B);
    if(deg[B] <= 4){
        disj.degcnt[p][deg[B]-1]--;
        disj.degcnt[p][deg[B]]++;
        if(deg[B] == 3) disj.repres3[p] = B;
        if(deg[B] == 4) disj.repres4[p] = B;
    }
    disj.uni(A,B);
    p = disj.find(A);
    if(disj.degcnt[p][3] || disj.degcnt[p][4] || (disj.degcnt[p][2] == disj.size[p])){
        if(focus == -1) focus = p;
        else{
            focus = disj.find(focus);
            if(focus != p){
                deadend = 1;
            }
        }
    }
}
 
bool vis[1000005];
queue<int> q;
 
bool tvis[1000005];
 
int solve(int x){
    memset(tvis,0,sizeof(tvis));
    tvis[x] = 1;
    int ret = 1;
    for(auto &i : graph[x]){
        deg[x]--;
        deg[i]--;
    }
    for(auto &i : graph[x]){
        if(tvis[i]) continue;
        tvis[i] = 1;
        q.push(i);
        int foundThree = 0, foundOne = 0, foundTwo = 0;
        while(!q.empty()){
            int qf = q.front();
            q.pop();
            if(deg[qf] >= 3) foundThree = 1;
            if(deg[qf] == 1) foundOne = 1;
            if(deg[qf] == 2) foundTwo = 1;
            for(auto &i : graph[qf]){
                if(!tvis[i]){
                    tvis[i] = 1;
                    q.push(i);
                }
            }
        }
        if(foundThree == 1){
            ret = 0;
            break;
        }
        if(foundTwo && !foundOne){
            ret = 0;
            break;
        }
    }
    for(auto &i : graph[x]){
        deg[x]++;
        deg[i]++;
    }
    return ret;
}
 
int CountCritical(){
    if(focus == -1) return n;
    if(deadend == 1) return 0;
    memset(vis,0,sizeof(vis));
    int ret = 0;
    if(disj.degcnt[focus][2] == disj.size[focus]){
        return disj.size[focus];
    }
    if(disj.degcnt[focus][4] == 1){
        return solve(disj.repres4[focus]);
    }
    int p = disj.repres3[focus];
    ret = solve(p);
    for(auto &i : graph[p]){
        if(solve(i)) ret++;
    }
    return ret;
}

Subtask #1
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	23800 KB	Output is correct
2	Correct	25 ms	26100 KB	Output is correct
3	Correct	25 ms	26264 KB	Output is correct
4	Correct	22 ms	26264 KB	Output is correct
5	Correct	24 ms	26264 KB	Output is correct
6	Correct	25 ms	26264 KB	Output is correct
7	Correct	22 ms	26264 KB	Output is correct
8	Correct	24 ms	26264 KB	Output is correct
9	Correct	26 ms	26420 KB	Output is correct
10	Correct	27 ms	26436 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	642 ms	60848 KB	Output is correct
2	Correct	1421 ms	82412 KB	Output is correct
3	Correct	1616 ms	90636 KB	Output is correct
4	Correct	1823 ms	95480 KB	Output is correct
5	Correct	1921 ms	95616 KB	Output is correct
6	Correct	1871 ms	95616 KB	Output is correct
7	Correct	1583 ms	95616 KB	Output is correct
8	Correct	1671 ms	95616 KB	Output is correct
9	Correct	1827 ms	96500 KB	Output is correct
10	Correct	1224 ms	96500 KB	Output is correct

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	23800 KB	Output is correct
2	Correct	25 ms	26100 KB	Output is correct
3	Correct	25 ms	26264 KB	Output is correct
4	Correct	22 ms	26264 KB	Output is correct
5	Correct	24 ms	26264 KB	Output is correct
6	Correct	25 ms	26264 KB	Output is correct
7	Correct	22 ms	26264 KB	Output is correct
8	Correct	24 ms	26264 KB	Output is correct
9	Correct	26 ms	26420 KB	Output is correct
10	Correct	27 ms	26436 KB	Output is correct
11	Correct	32 ms	96500 KB	Output is correct
12	Correct	32 ms	96500 KB	Output is correct
13	Correct	37 ms	96500 KB	Output is correct
14	Correct	44 ms	96500 KB	Output is correct
15	Correct	48 ms	96500 KB	Output is correct
16	Correct	40 ms	96500 KB	Output is correct
17	Correct	28 ms	96500 KB	Output is correct
18	Correct	28 ms	96500 KB	Output is correct
19	Correct	29 ms	96500 KB	Output is correct
20	Correct	42 ms	96500 KB	Output is correct

Subtask #4
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	23800 KB	Output is correct
2	Correct	25 ms	26100 KB	Output is correct
3	Correct	25 ms	26264 KB	Output is correct
4	Correct	22 ms	26264 KB	Output is correct
5	Correct	24 ms	26264 KB	Output is correct
6	Correct	25 ms	26264 KB	Output is correct
7	Correct	22 ms	26264 KB	Output is correct
8	Correct	24 ms	26264 KB	Output is correct
9	Correct	26 ms	26420 KB	Output is correct
10	Correct	27 ms	26436 KB	Output is correct
11	Correct	32 ms	96500 KB	Output is correct
12	Correct	32 ms	96500 KB	Output is correct
13	Correct	37 ms	96500 KB	Output is correct
14	Correct	44 ms	96500 KB	Output is correct
15	Correct	48 ms	96500 KB	Output is correct
16	Correct	40 ms	96500 KB	Output is correct
17	Correct	28 ms	96500 KB	Output is correct
18	Correct	28 ms	96500 KB	Output is correct
19	Correct	29 ms	96500 KB	Output is correct
20	Correct	42 ms	96500 KB	Output is correct
21	Correct	48 ms	96500 KB	Output is correct
22	Correct	63 ms	96500 KB	Output is correct
23	Correct	78 ms	96500 KB	Output is correct
24	Execution timed out	4009 ms	96500 KB	Time limit exceeded
25	Halted	0 ms	0 KB	-

Subtask #5
0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	23800 KB	Output is correct
2	Correct	25 ms	26100 KB	Output is correct
3	Correct	25 ms	26264 KB	Output is correct
4	Correct	22 ms	26264 KB	Output is correct
5	Correct	24 ms	26264 KB	Output is correct
6	Correct	25 ms	26264 KB	Output is correct
7	Correct	22 ms	26264 KB	Output is correct
8	Correct	24 ms	26264 KB	Output is correct
9	Correct	26 ms	26420 KB	Output is correct
10	Correct	27 ms	26436 KB	Output is correct
11	Correct	642 ms	60848 KB	Output is correct
12	Correct	1421 ms	82412 KB	Output is correct
13	Correct	1616 ms	90636 KB	Output is correct
14	Correct	1823 ms	95480 KB	Output is correct
15	Correct	1921 ms	95616 KB	Output is correct
16	Correct	1871 ms	95616 KB	Output is correct
17	Correct	1583 ms	95616 KB	Output is correct
18	Correct	1671 ms	95616 KB	Output is correct
19	Correct	1827 ms	96500 KB	Output is correct
20	Correct	1224 ms	96500 KB	Output is correct
21	Correct	32 ms	96500 KB	Output is correct
22	Correct	32 ms	96500 KB	Output is correct
23	Correct	37 ms	96500 KB	Output is correct
24	Correct	44 ms	96500 KB	Output is correct
25	Correct	48 ms	96500 KB	Output is correct
26	Correct	40 ms	96500 KB	Output is correct
27	Correct	28 ms	96500 KB	Output is correct
28	Correct	28 ms	96500 KB	Output is correct
29	Correct	29 ms	96500 KB	Output is correct
30	Correct	42 ms	96500 KB	Output is correct
31	Correct	48 ms	96500 KB	Output is correct
32	Correct	63 ms	96500 KB	Output is correct
33	Correct	78 ms	96500 KB	Output is correct
34	Execution timed out	4009 ms	96500 KB	Time limit exceeded
35	Halted	0 ms	0 KB	-

답안 #15597

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 17.0 / 17.0

Subtask #3 18.0 / 18.0

Subtask #4 0 / 14.0

Subtask #5 0 / 31.0

Subtask #1
20.0 / 20.0

Subtask #2
17.0 / 17.0

Subtask #3
18.0 / 18.0

Subtask #4
0 / 14.0

Subtask #5
0 / 31.0