답안 #15609 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
15609	2015-07-13T10:18:26 Z	gs14004	낙하산 고리들 (IOI12_rings)	C++14	100 / 100	1912 ms	85884 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	21 ms	23800 KB	Output is correct
2	Correct	23 ms	24052 KB	Output is correct
3	Correct	22 ms	24216 KB	Output is correct
4	Correct	21 ms	24216 KB	Output is correct
5	Correct	22 ms	24216 KB	Output is correct
6	Correct	23 ms	24216 KB	Output is correct
7	Correct	22 ms	24240 KB	Output is correct
8	Correct	23 ms	24240 KB	Output is correct
9	Correct	24 ms	24372 KB	Output is correct
10	Correct	24 ms	24372 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	485 ms	44484 KB	Output is correct
2	Correct	832 ms	63152 KB	Output is correct
3	Correct	355 ms	63152 KB	Output is correct
4	Correct	1254 ms	63268 KB	Output is correct
5	Correct	1255 ms	63268 KB	Output is correct
6	Correct	1464 ms	63268 KB	Output is correct
7	Correct	363 ms	63268 KB	Output is correct
8	Correct	1563 ms	79868 KB	Output is correct
9	Correct	1912 ms	85884 KB	Output is correct
10	Correct	848 ms	85884 KB	Output is correct

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	23800 KB	Output is correct
2	Correct	23 ms	24052 KB	Output is correct
3	Correct	22 ms	24216 KB	Output is correct
4	Correct	21 ms	24216 KB	Output is correct
5	Correct	22 ms	24216 KB	Output is correct
6	Correct	23 ms	24216 KB	Output is correct
7	Correct	22 ms	24240 KB	Output is correct
8	Correct	23 ms	24240 KB	Output is correct
9	Correct	24 ms	24372 KB	Output is correct
10	Correct	24 ms	24372 KB	Output is correct
11	Correct	59 ms	85884 KB	Output is correct
12	Correct	28 ms	85884 KB	Output is correct
13	Correct	27 ms	85884 KB	Output is correct
14	Correct	31 ms	85884 KB	Output is correct
15	Correct	32 ms	85884 KB	Output is correct
16	Correct	35 ms	85884 KB	Output is correct
17	Correct	25 ms	85884 KB	Output is correct
18	Correct	26 ms	85884 KB	Output is correct
19	Correct	28 ms	85884 KB	Output is correct
20	Correct	26 ms	85884 KB	Output is correct

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	23800 KB	Output is correct
2	Correct	23 ms	24052 KB	Output is correct
3	Correct	22 ms	24216 KB	Output is correct
4	Correct	21 ms	24216 KB	Output is correct
5	Correct	22 ms	24216 KB	Output is correct
6	Correct	23 ms	24216 KB	Output is correct
7	Correct	22 ms	24240 KB	Output is correct
8	Correct	23 ms	24240 KB	Output is correct
9	Correct	24 ms	24372 KB	Output is correct
10	Correct	24 ms	24372 KB	Output is correct
11	Correct	59 ms	85884 KB	Output is correct
12	Correct	28 ms	85884 KB	Output is correct
13	Correct	27 ms	85884 KB	Output is correct
14	Correct	31 ms	85884 KB	Output is correct
15	Correct	32 ms	85884 KB	Output is correct
16	Correct	35 ms	85884 KB	Output is correct
17	Correct	25 ms	85884 KB	Output is correct
18	Correct	26 ms	85884 KB	Output is correct
19	Correct	28 ms	85884 KB	Output is correct
20	Correct	26 ms	85884 KB	Output is correct
21	Correct	28 ms	85884 KB	Output is correct
22	Correct	56 ms	85884 KB	Output is correct
23	Correct	72 ms	85884 KB	Output is correct
24	Correct	52 ms	85884 KB	Output is correct
25	Correct	38 ms	85884 KB	Output is correct
26	Correct	53 ms	85884 KB	Output is correct
27	Correct	78 ms	85884 KB	Output is correct
28	Correct	53 ms	85884 KB	Output is correct
29	Correct	50 ms	85884 KB	Output is correct
30	Correct	92 ms	85884 KB	Output is correct

Subtask #5
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	23800 KB	Output is correct
2	Correct	23 ms	24052 KB	Output is correct
3	Correct	22 ms	24216 KB	Output is correct
4	Correct	21 ms	24216 KB	Output is correct
5	Correct	22 ms	24216 KB	Output is correct
6	Correct	23 ms	24216 KB	Output is correct
7	Correct	22 ms	24240 KB	Output is correct
8	Correct	23 ms	24240 KB	Output is correct
9	Correct	24 ms	24372 KB	Output is correct
10	Correct	24 ms	24372 KB	Output is correct
11	Correct	485 ms	44484 KB	Output is correct
12	Correct	832 ms	63152 KB	Output is correct
13	Correct	355 ms	63152 KB	Output is correct
14	Correct	1254 ms	63268 KB	Output is correct
15	Correct	1255 ms	63268 KB	Output is correct
16	Correct	1464 ms	63268 KB	Output is correct
17	Correct	363 ms	63268 KB	Output is correct
18	Correct	1563 ms	79868 KB	Output is correct
19	Correct	1912 ms	85884 KB	Output is correct
20	Correct	848 ms	85884 KB	Output is correct
21	Correct	59 ms	85884 KB	Output is correct
22	Correct	28 ms	85884 KB	Output is correct
23	Correct	27 ms	85884 KB	Output is correct
24	Correct	31 ms	85884 KB	Output is correct
25	Correct	32 ms	85884 KB	Output is correct
26	Correct	35 ms	85884 KB	Output is correct
27	Correct	25 ms	85884 KB	Output is correct
28	Correct	26 ms	85884 KB	Output is correct
29	Correct	28 ms	85884 KB	Output is correct
30	Correct	26 ms	85884 KB	Output is correct
31	Correct	28 ms	85884 KB	Output is correct
32	Correct	56 ms	85884 KB	Output is correct
33	Correct	72 ms	85884 KB	Output is correct
34	Correct	52 ms	85884 KB	Output is correct
35	Correct	38 ms	85884 KB	Output is correct
36	Correct	53 ms	85884 KB	Output is correct
37	Correct	78 ms	85884 KB	Output is correct
38	Correct	53 ms	85884 KB	Output is correct
39	Correct	50 ms	85884 KB	Output is correct
40	Correct	92 ms	85884 KB	Output is correct
41	Correct	259 ms	85884 KB	Output is correct
42	Correct	796 ms	85884 KB	Output is correct
43	Correct	265 ms	85884 KB	Output is correct
44	Correct	357 ms	85884 KB	Output is correct
45	Correct	505 ms	85884 KB	Output is correct
46	Correct	803 ms	85884 KB	Output is correct
47	Correct	1209 ms	85884 KB	Output is correct
48	Correct	315 ms	85884 KB	Output is correct
49	Correct	821 ms	85884 KB	Output is correct
50	Correct	869 ms	85884 KB	Output is correct
51	Correct	255 ms	85884 KB	Output is correct
52	Correct	338 ms	85884 KB	Output is correct
53	Correct	279 ms	85884 KB	Output is correct
54	Correct	1263 ms	85884 KB	Output is correct
55	Correct	485 ms	85884 KB	Output is correct

답안 #15609

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