답안 #62491 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62491	2018-07-28T19:11:42 Z	zetapi	낙하산 고리들 (IOI12_rings)	C++14	100 / 100	2047 ms	85756 KB

rings

/*
    O(N+M+C) solution for Rings (N = number of vertices; M = number of calls to Link; C = number of calls to CountCritical).
     
    Author: Giovanni Paolini
*/
 
#include <cstdio>
#include <vector>
#include <cassert>
 
 
using namespace std;
 
int const MAXN = 1000000;
 
int n;
bool quadruplication = 0;
 
int numcycles = 0;
int cycle_length; // If numcycles==1, here we store the length of the only cycle
 
int other_endpoint[4][MAXN]; // -1 if the node is not an endpoint, otherwise the other endpoint
vector<int> neighbours[MAXN];
 
int destroyed[4]; // The destroyed node of each graph (only if quadruplication==TRUE)
int degree[4][MAXN];
bool islinear[4]; // Whether each graph is linear or not
 
void Init(int k) {
    n = k;
     
    for (int i=0; i<n; ++i) {
        other_endpoint[0][i] = i;
    }
}
 
void add_new_edge(int x, int y) {
    // Adds an edge in case of quadruplication
     
    for (int i=0; i<4; ++i) {
         
        // Operating on graph i
         
        if ( !islinear[i] ) continue;
        if ( x == destroyed[i] || y == destroyed[i] ) continue;
         
        degree[i][x]++;
        degree[i][y]++;
         
        assert( degree[i][x] <= 3 && degree[i][y] <= 3 );
         
        if ( degree[i][x] == 3 || degree[i][y] == 3 ) {
            islinear[i] = 0;
            continue;
        }
         
        if ( other_endpoint[i][x] == y ) {
            // Cycle!
             
            islinear[i] = 0;
            continue;
        }
         
         
         
        int a = other_endpoint[i][x];
        int b = other_endpoint[i][y];
         
        other_endpoint[i][x] = -1;
        other_endpoint[i][y] = -1;
        other_endpoint[i][a] = b;
        other_endpoint[i][b] = a;
         
    }
     
}
 
 
void quadruplicate (int x) {
     
    quadruplication = 1;
     
    destroyed[0] = x;
    destroyed[1] = neighbours[x][0];
    destroyed[2] = neighbours[x][1];
    destroyed[3] = neighbours[x][2];
     
    for (int i=0; i<4; ++i) {
        for (int j=0; j<n; ++j) {
            other_endpoint[i][j] = j;
            degree[i][j] = 0;
        }
    }
     
    for (int i=0; i<4; ++i) {
        islinear[i] = 1;
    }
     
    for (int k=0; k<n; ++k) {
        for (vector<int>::iterator j = neighbours[k].begin(); j != neighbours[k].end(); ++j) {
             
            if ( k < (*j) )  add_new_edge( k, (*j) );
             
        }
    }
     
}
 
void Link(int xx, int yy) {
     
    int x = xx;
    int y = yy;
     
    if ( quadruplication == 0 ) {
         
        neighbours[x].push_back(y);
        neighbours[y].push_back(x);
         
        degree[0][x]++;
        degree[0][y]++;
         
        // If a node has degree 3, only it or its neighbours can be critical. So we can keep track of each of the 4 graphs obtained by removing one of these 4 nodes.
        if ( degree[0][x] == 3 ) {
            quadruplicate(x);
            return;
        }
        if ( degree[0][y] == 3 ) {
            quadruplicate(y);
            return;
        }
         
        // If their degree is < 3, then they were necessarily endpoints!
         
        if ( other_endpoint[0][x] != y ) { // A longer path is formed
            int a = other_endpoint[0][x];
            int b = other_endpoint[0][y];
             
            other_endpoint[0][x] = -1;
            other_endpoint[0][y] = -1;
            other_endpoint[0][a] = b;
            other_endpoint[0][b] = a;
        }
        else {  // A cycle is formed
            numcycles++;
            if ( numcycles == 1 ) {
                 
                int length = 1;
                int previous_node = x;
                int current_node = neighbours[x][0];
                 
                while ( current_node != x ) {
                    int possibility = neighbours[ current_node ][0];
                    if ( possibility == previous_node ) possibility = neighbours[ current_node ][1];
                     
                    previous_node = current_node;
                    current_node = possibility;
                     
                    length++;
                }
                 
                cycle_length = length;
                 
            }
        }
    }
     
    else {
         
        add_new_edge(x,y);
         
    }
}
 
int CountCritical() {
     
    if ( quadruplication == 0 ) {
         
        switch (numcycles) {
            case 0:
                return n;
             
            case 1:
                return cycle_length;
             
            default:
                return 0;
        }
         
    }
    else {
         
        int answer = 0;
        for (int i=0; i<4; ++i) {
            if ( islinear[i] ) answer++;
        }
        return answer;
         
    }
}

Subtask #1
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23800 KB	Output is correct
2	Correct	24 ms	24188 KB	Output is correct
3	Correct	29 ms	24232 KB	Output is correct
4	Correct	21 ms	24232 KB	Output is correct
5	Correct	23 ms	24232 KB	Output is correct
6	Correct	25 ms	24276 KB	Output is correct
7	Correct	21 ms	24276 KB	Output is correct
8	Correct	32 ms	24276 KB	Output is correct
9	Correct	24 ms	24416 KB	Output is correct
10	Correct	23 ms	24428 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	448 ms	44652 KB	Output is correct
2	Correct	784 ms	63212 KB	Output is correct
3	Correct	375 ms	63212 KB	Output is correct
4	Correct	1239 ms	63352 KB	Output is correct
5	Correct	1247 ms	63416 KB	Output is correct
6	Correct	1342 ms	63416 KB	Output is correct
7	Correct	359 ms	63416 KB	Output is correct
8	Correct	1636 ms	79868 KB	Output is correct
9	Correct	2047 ms	85756 KB	Output is correct
10	Correct	825 ms	85756 KB	Output is correct

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23800 KB	Output is correct
2	Correct	24 ms	24188 KB	Output is correct
3	Correct	29 ms	24232 KB	Output is correct
4	Correct	21 ms	24232 KB	Output is correct
5	Correct	23 ms	24232 KB	Output is correct
6	Correct	25 ms	24276 KB	Output is correct
7	Correct	21 ms	24276 KB	Output is correct
8	Correct	32 ms	24276 KB	Output is correct
9	Correct	24 ms	24416 KB	Output is correct
10	Correct	23 ms	24428 KB	Output is correct
11	Correct	23 ms	85756 KB	Output is correct
12	Correct	27 ms	85756 KB	Output is correct
13	Correct	26 ms	85756 KB	Output is correct
14	Correct	24 ms	85756 KB	Output is correct
15	Correct	32 ms	85756 KB	Output is correct
16	Correct	36 ms	85756 KB	Output is correct
17	Correct	25 ms	85756 KB	Output is correct
18	Correct	27 ms	85756 KB	Output is correct
19	Correct	28 ms	85756 KB	Output is correct
20	Correct	27 ms	85756 KB	Output is correct

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23800 KB	Output is correct
2	Correct	24 ms	24188 KB	Output is correct
3	Correct	29 ms	24232 KB	Output is correct
4	Correct	21 ms	24232 KB	Output is correct
5	Correct	23 ms	24232 KB	Output is correct
6	Correct	25 ms	24276 KB	Output is correct
7	Correct	21 ms	24276 KB	Output is correct
8	Correct	32 ms	24276 KB	Output is correct
9	Correct	24 ms	24416 KB	Output is correct
10	Correct	23 ms	24428 KB	Output is correct
11	Correct	23 ms	85756 KB	Output is correct
12	Correct	27 ms	85756 KB	Output is correct
13	Correct	26 ms	85756 KB	Output is correct
14	Correct	24 ms	85756 KB	Output is correct
15	Correct	32 ms	85756 KB	Output is correct
16	Correct	36 ms	85756 KB	Output is correct
17	Correct	25 ms	85756 KB	Output is correct
18	Correct	27 ms	85756 KB	Output is correct
19	Correct	28 ms	85756 KB	Output is correct
20	Correct	27 ms	85756 KB	Output is correct
21	Correct	42 ms	85756 KB	Output is correct
22	Correct	56 ms	85756 KB	Output is correct
23	Correct	73 ms	85756 KB	Output is correct
24	Correct	52 ms	85756 KB	Output is correct
25	Correct	36 ms	85756 KB	Output is correct
26	Correct	56 ms	85756 KB	Output is correct
27	Correct	76 ms	85756 KB	Output is correct
28	Correct	52 ms	85756 KB	Output is correct
29	Correct	49 ms	85756 KB	Output is correct
30	Correct	125 ms	85756 KB	Output is correct

Subtask #5
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	23800 KB	Output is correct
2	Correct	24 ms	24188 KB	Output is correct
3	Correct	29 ms	24232 KB	Output is correct
4	Correct	21 ms	24232 KB	Output is correct
5	Correct	23 ms	24232 KB	Output is correct
6	Correct	25 ms	24276 KB	Output is correct
7	Correct	21 ms	24276 KB	Output is correct
8	Correct	32 ms	24276 KB	Output is correct
9	Correct	24 ms	24416 KB	Output is correct
10	Correct	23 ms	24428 KB	Output is correct
11	Correct	448 ms	44652 KB	Output is correct
12	Correct	784 ms	63212 KB	Output is correct
13	Correct	375 ms	63212 KB	Output is correct
14	Correct	1239 ms	63352 KB	Output is correct
15	Correct	1247 ms	63416 KB	Output is correct
16	Correct	1342 ms	63416 KB	Output is correct
17	Correct	359 ms	63416 KB	Output is correct
18	Correct	1636 ms	79868 KB	Output is correct
19	Correct	2047 ms	85756 KB	Output is correct
20	Correct	825 ms	85756 KB	Output is correct
21	Correct	23 ms	85756 KB	Output is correct
22	Correct	27 ms	85756 KB	Output is correct
23	Correct	26 ms	85756 KB	Output is correct
24	Correct	24 ms	85756 KB	Output is correct
25	Correct	32 ms	85756 KB	Output is correct
26	Correct	36 ms	85756 KB	Output is correct
27	Correct	25 ms	85756 KB	Output is correct
28	Correct	27 ms	85756 KB	Output is correct
29	Correct	28 ms	85756 KB	Output is correct
30	Correct	27 ms	85756 KB	Output is correct
31	Correct	42 ms	85756 KB	Output is correct
32	Correct	56 ms	85756 KB	Output is correct
33	Correct	73 ms	85756 KB	Output is correct
34	Correct	52 ms	85756 KB	Output is correct
35	Correct	36 ms	85756 KB	Output is correct
36	Correct	56 ms	85756 KB	Output is correct
37	Correct	76 ms	85756 KB	Output is correct
38	Correct	52 ms	85756 KB	Output is correct
39	Correct	49 ms	85756 KB	Output is correct
40	Correct	125 ms	85756 KB	Output is correct
41	Correct	262 ms	85756 KB	Output is correct
42	Correct	789 ms	85756 KB	Output is correct
43	Correct	268 ms	85756 KB	Output is correct
44	Correct	341 ms	85756 KB	Output is correct
45	Correct	484 ms	85756 KB	Output is correct
46	Correct	785 ms	85756 KB	Output is correct
47	Correct	1196 ms	85756 KB	Output is correct
48	Correct	311 ms	85756 KB	Output is correct
49	Correct	790 ms	85756 KB	Output is correct
50	Correct	865 ms	85756 KB	Output is correct
51	Correct	256 ms	85756 KB	Output is correct
52	Correct	315 ms	85756 KB	Output is correct
53	Correct	326 ms	85756 KB	Output is correct
54	Correct	1266 ms	85756 KB	Output is correct
55	Correct	526 ms	85756 KB	Output is correct

답안 #62491

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