답안 #90267 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90267	2018-12-21T03:03:44 Z	Retro3014	게임 (IOI14_game)	C++17	100 / 100	623 ms	159956 KB

game

#include "game.h"
#include <vector>


using namespace std;
#define MAX_N 1500

int group[MAX_N+1];
bool b[MAX_N+1];
int num[MAX_N+1];
int graph[MAX_N+1][MAX_N+1];

vector<int> v;
int N;

int findg(int x){
    if(group[x]==group[group[x]]){
        return group[x];
    }
    while(x!=group[x]){
        v.push_back(x);
        x=group[x];
    }
    while(!v.empty()){
        group[v.back()]=x;
        v.pop_back();
    }
    return x;
}

bool mrg(int x, int y){
    x=findg(x); y=findg(y);
    if(x==y){
        return false;
    }
    if(graph[x][y]>1){
        graph[x][y]--;
        graph[y][x]--;
        return false;
    }
    if(graph[x][y]==1){
        graph[x][y]--;
        graph[y][x]--;
        if(num[x]>num[y]){
            int tmp=x;x=y;y=tmp;
        }
        group[x]=y;
        num[y]+=num[x];
        b[x]=false;
        for(int i=0; i<N; i++){
            if(b[i]){
                graph[y][i]+=graph[x][i];
                graph[i][y]=graph[y][i];
                graph[x][i]=0;
                graph[i][x]=0;
            }
        }
        return true;
    }
    return false;
}


void initialize(int n) {
    N=n;
    for(int i=0; i<N; i++){
        num[i]=1;
        group[i]=i;
        b[i]=true;
    }
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(i!=j){
                graph[i][j]=1;
            }
        }
    }
}

int hasEdge(int u, int v) {
    return mrg(u, v);
}

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	380 KB	Output is correct
2	Correct	1 ms	380 KB	Output is correct
3	Correct	1 ms	408 KB	Output is correct
4	Correct	2 ms	408 KB	Output is correct
5	Correct	2 ms	468 KB	Output is correct
6	Correct	2 ms	468 KB	Output is correct
7	Correct	1 ms	484 KB	Output is correct
8	Correct	2 ms	500 KB	Output is correct
9	Correct	2 ms	504 KB	Output is correct
10	Correct	2 ms	504 KB	Output is correct
11	Correct	2 ms	612 KB	Output is correct
12	Correct	2 ms	696 KB	Output is correct
13	Correct	2 ms	696 KB	Output is correct
14	Correct	2 ms	696 KB	Output is correct
15	Correct	2 ms	696 KB	Output is correct
16	Correct	2 ms	696 KB	Output is correct
17	Correct	2 ms	696 KB	Output is correct
18	Correct	2 ms	696 KB	Output is correct
19	Correct	2 ms	696 KB	Output is correct
20	Correct	2 ms	696 KB	Output is correct
21	Correct	2 ms	696 KB	Output is correct
22	Correct	2 ms	696 KB	Output is correct
23	Correct	2 ms	696 KB	Output is correct
24	Correct	2 ms	696 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	696 KB	Output is correct
2	Correct	2 ms	696 KB	Output is correct
3	Correct	1 ms	696 KB	Output is correct
4	Correct	2 ms	696 KB	Output is correct
5	Correct	2 ms	696 KB	Output is correct
6	Correct	2 ms	696 KB	Output is correct
7	Correct	2 ms	696 KB	Output is correct
8	Correct	2 ms	696 KB	Output is correct
9	Correct	2 ms	696 KB	Output is correct
10	Correct	2 ms	696 KB	Output is correct
11	Correct	2 ms	696 KB	Output is correct
12	Correct	2 ms	696 KB	Output is correct
13	Correct	2 ms	696 KB	Output is correct
14	Correct	2 ms	696 KB	Output is correct
15	Correct	1 ms	696 KB	Output is correct
16	Correct	2 ms	696 KB	Output is correct
17	Correct	2 ms	696 KB	Output is correct
18	Correct	2 ms	696 KB	Output is correct
19	Correct	1 ms	696 KB	Output is correct
20	Correct	1 ms	696 KB	Output is correct
21	Correct	1 ms	696 KB	Output is correct
22	Correct	2 ms	696 KB	Output is correct
23	Correct	1 ms	696 KB	Output is correct
24	Correct	1 ms	696 KB	Output is correct
25	Correct	2 ms	764 KB	Output is correct
26	Correct	2 ms	892 KB	Output is correct
27	Correct	2 ms	892 KB	Output is correct
28	Correct	2 ms	892 KB	Output is correct
29	Correct	2 ms	892 KB	Output is correct
30	Correct	10 ms	892 KB	Output is correct
31	Correct	2 ms	892 KB	Output is correct
32	Correct	2 ms	892 KB	Output is correct
33	Correct	2 ms	892 KB	Output is correct
34	Correct	3 ms	1084 KB	Output is correct
35	Correct	3 ms	1120 KB	Output is correct
36	Correct	3 ms	1120 KB	Output is correct
37	Correct	3 ms	1120 KB	Output is correct
38	Correct	3 ms	1232 KB	Output is correct
39	Correct	3 ms	1232 KB	Output is correct
40	Correct	3 ms	1304 KB	Output is correct
41	Correct	3 ms	1304 KB	Output is correct
42	Correct	3 ms	1304 KB	Output is correct
43	Correct	3 ms	1304 KB	Output is correct
44	Correct	3 ms	1304 KB	Output is correct
45	Correct	3 ms	1304 KB	Output is correct
46	Correct	3 ms	1312 KB	Output is correct
47	Correct	3 ms	1332 KB	Output is correct
48	Correct	3 ms	1352 KB	Output is correct
49	Correct	3 ms	1372 KB	Output is correct
50	Correct	3 ms	1508 KB	Output is correct
51	Correct	3 ms	1508 KB	Output is correct
52	Correct	3 ms	1508 KB	Output is correct
53	Correct	3 ms	1508 KB	Output is correct
54	Correct	3 ms	1508 KB	Output is correct

Subtask #3
58.0 / 58.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1508 KB	Output is correct
2	Correct	2 ms	1508 KB	Output is correct
3	Correct	2 ms	1508 KB	Output is correct
4	Correct	2 ms	1508 KB	Output is correct
5	Correct	2 ms	1508 KB	Output is correct
6	Correct	2 ms	1508 KB	Output is correct
7	Correct	2 ms	1508 KB	Output is correct
8	Correct	2 ms	1508 KB	Output is correct
9	Correct	2 ms	1508 KB	Output is correct
10	Correct	2 ms	1508 KB	Output is correct
11	Correct	2 ms	1508 KB	Output is correct
12	Correct	2 ms	1508 KB	Output is correct
13	Correct	2 ms	1508 KB	Output is correct
14	Correct	1 ms	1508 KB	Output is correct
15	Correct	2 ms	1508 KB	Output is correct
16	Correct	2 ms	1508 KB	Output is correct
17	Correct	2 ms	1508 KB	Output is correct
18	Correct	2 ms	1508 KB	Output is correct
19	Correct	2 ms	1508 KB	Output is correct
20	Correct	2 ms	1508 KB	Output is correct
21	Correct	2 ms	1508 KB	Output is correct
22	Correct	2 ms	1508 KB	Output is correct
23	Correct	2 ms	1508 KB	Output is correct
24	Correct	2 ms	1508 KB	Output is correct
25	Correct	2 ms	1508 KB	Output is correct
26	Correct	2 ms	1508 KB	Output is correct
27	Correct	2 ms	1508 KB	Output is correct
28	Correct	2 ms	1508 KB	Output is correct
29	Correct	2 ms	1508 KB	Output is correct
30	Correct	2 ms	1508 KB	Output is correct
31	Correct	2 ms	1508 KB	Output is correct
32	Correct	2 ms	1512 KB	Output is correct
33	Correct	2 ms	1512 KB	Output is correct
34	Correct	3 ms	1652 KB	Output is correct
35	Correct	3 ms	1676 KB	Output is correct
36	Correct	3 ms	1696 KB	Output is correct
37	Correct	3 ms	1696 KB	Output is correct
38	Correct	3 ms	1696 KB	Output is correct
39	Correct	3 ms	1696 KB	Output is correct
40	Correct	3 ms	1696 KB	Output is correct
41	Correct	3 ms	1696 KB	Output is correct
42	Correct	3 ms	1840 KB	Output is correct
43	Correct	2 ms	1840 KB	Output is correct
44	Correct	2 ms	1840 KB	Output is correct
45	Correct	3 ms	1840 KB	Output is correct
46	Correct	0 ms	1840 KB	Output is correct
47	Correct	3 ms	1840 KB	Output is correct
48	Correct	3 ms	1840 KB	Output is correct
49	Correct	3 ms	1844 KB	Output is correct
50	Correct	3 ms	1864 KB	Output is correct
51	Correct	3 ms	1884 KB	Output is correct
52	Correct	3 ms	1904 KB	Output is correct
53	Correct	3 ms	2056 KB	Output is correct
54	Correct	2 ms	2056 KB	Output is correct
55	Correct	44 ms	6448 KB	Output is correct
56	Correct	44 ms	7420 KB	Output is correct
57	Correct	45 ms	8396 KB	Output is correct
58	Correct	46 ms	9372 KB	Output is correct
59	Correct	45 ms	10348 KB	Output is correct
60	Correct	46 ms	11372 KB	Output is correct
61	Correct	46 ms	12392 KB	Output is correct
62	Correct	46 ms	13276 KB	Output is correct
63	Correct	46 ms	14252 KB	Output is correct
64	Correct	41 ms	15244 KB	Output is correct
65	Correct	40 ms	16180 KB	Output is correct
66	Correct	45 ms	17252 KB	Output is correct
67	Correct	46 ms	18188 KB	Output is correct
68	Correct	59 ms	19164 KB	Output is correct
69	Correct	50 ms	20148 KB	Output is correct
70	Correct	46 ms	21116 KB	Output is correct
71	Correct	44 ms	22092 KB	Output is correct
72	Correct	44 ms	23160 KB	Output is correct
73	Correct	44 ms	24008 KB	Output is correct
74	Correct	45 ms	25036 KB	Output is correct
75	Correct	45 ms	26012 KB	Output is correct
76	Correct	104 ms	30792 KB	Output is correct
77	Correct	100 ms	33124 KB	Output is correct
78	Correct	100 ms	35344 KB	Output is correct
79	Correct	99 ms	37788 KB	Output is correct
80	Correct	97 ms	40060 KB	Output is correct
81	Correct	98 ms	42236 KB	Output is correct
82	Correct	97 ms	44524 KB	Output is correct
83	Correct	98 ms	46796 KB	Output is correct
84	Correct	98 ms	49084 KB	Output is correct
85	Correct	183 ms	55836 KB	Output is correct
86	Correct	176 ms	59876 KB	Output is correct
87	Correct	197 ms	63916 KB	Output is correct
88	Correct	203 ms	67924 KB	Output is correct
89	Correct	198 ms	71996 KB	Output is correct
90	Correct	213 ms	75976 KB	Output is correct
91	Correct	204 ms	80000 KB	Output is correct
92	Correct	204 ms	84024 KB	Output is correct
93	Correct	212 ms	88048 KB	Output is correct
94	Correct	588 ms	103864 KB	Output is correct
95	Correct	604 ms	113188 KB	Output is correct
96	Correct	602 ms	122608 KB	Output is correct
97	Correct	623 ms	132076 KB	Output is correct
98	Correct	613 ms	141204 KB	Output is correct
99	Correct	588 ms	150588 KB	Output is correct
100	Correct	493 ms	159956 KB	Output is correct

답안 #90267

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 27.0 / 27.0

Subtask #3 58.0 / 58.0

Subtask #1
15.0 / 15.0

Subtask #2
27.0 / 27.0

Subtask #3
58.0 / 58.0