답안 #69929 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69929	2018-08-22T04:14:59 Z	top34051	Simurgh (IOI17_simurgh)	C++17	51 / 100	260 ms	6580 KB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 500 + 5;
const int maxm = 250000 + 5;

int n,m;

pii e[maxm];
int head[maxn];
int act[maxm], pos[maxm];
vector<int> tree;

vector<pii> way[maxn];
int par[maxn], come[maxn];

vector<int> path;
int rec[maxm];

int res[maxm];

int ask(int last, int id) {
    if(last==-1 || id==-1 || res[last]==-1 || res[id]==-1) {
        return count_common_roads(tree);
    }
    return rec[last] + res[last] - res[id];
}

int findhead(int x) {
	if(x==head[x]) return x;
	return head[x] = findhead(head[x]);
}

void dfs(int u, int last, int id) {
	par[u] = last; come[u] = id;
	for(auto t : way[u]) {
		int v = t.X, tid = t.Y;
		if(v==last) continue;
		dfs(v,u,tid);
	}
}

void prep(int x, int y) {
	dfs(x,-1,0);
	path.clear();
	for(int i=y;i!=x;i=par[i]) {
//		printf("%d %d : %d\n",par[i],i,come[i]);
		path.push_back(come[i]);
	}
}

vector<int> find_roads(int N, vector<int> U, vector<int> V) {
	n = N; m = U.size();
	for(int i=0;i<n;i++) head[i] = i;
	for(int i=0;i<m;i++) {
		int u = U[i], v = V[i];
		e[i] = {u,v};
		pos[i] = -1;
		if(findhead(u)!=findhead(v)) {
			head[findhead(u)] = findhead(v);
			pos[i] = tree.size();
			tree.push_back(i);
			way[u].push_back({v,i});
			way[v].push_back({u,i});
		}
        res[i] = -1;
	}

	int ori = ask(-1,-1);
//	printf("ori = %d\n",ori);

	for(int i=0;i<m;i++) {
		if(pos[i]!=-1) continue;
		int u = e[i].X, v = e[i].Y;
		prep(u,v);
		int last = -1;
//		printf("edge %d\n",i);
		for(auto id : path) {
			tree[pos[id]] = i;
			rec[id] = ask(last,id);
//			printf("\trec %d = %d\n",id,rec[id]);
			tree[pos[id]] = id;
			last = id;
		}

		res[i] = 0;
		for(auto id : path) {
			if(rec[id]-ori == 1) res[i] = 1;
		}
//		printf("\t\tres = %d\n",res[i]);

		for(auto id : path) {
            res[id] = ori + res[i] - rec[id];
//            printf("\t\tres %d = %d\n",id,res[id]);
		}
	}

	vector<int> vec;
	for(int i=0;i<m;i++) if(res[i]) vec.push_back(i);
//	for(auto t : vec) printf("%d ",t);
	return vec;
}

Subtask #1
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	correct
2	Correct	3 ms	488 KB	correct
3	Correct	2 ms	488 KB	correct
4	Correct	2 ms	488 KB	correct
5	Correct	3 ms	496 KB	correct
6	Correct	4 ms	496 KB	correct
7	Correct	2 ms	616 KB	correct
8	Correct	2 ms	736 KB	correct
9	Correct	2 ms	736 KB	correct
10	Correct	3 ms	736 KB	correct
11	Correct	3 ms	736 KB	correct
12	Correct	3 ms	736 KB	correct
13	Correct	3 ms	760 KB	correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	correct
2	Correct	3 ms	488 KB	correct
3	Correct	2 ms	488 KB	correct
4	Correct	2 ms	488 KB	correct
5	Correct	3 ms	496 KB	correct
6	Correct	4 ms	496 KB	correct
7	Correct	2 ms	616 KB	correct
8	Correct	2 ms	736 KB	correct
9	Correct	2 ms	736 KB	correct
10	Correct	3 ms	736 KB	correct
11	Correct	3 ms	736 KB	correct
12	Correct	3 ms	736 KB	correct
13	Correct	3 ms	760 KB	correct
14	Correct	5 ms	760 KB	correct
15	Correct	6 ms	780 KB	correct
16	Correct	5 ms	780 KB	correct
17	Correct	4 ms	780 KB	correct
18	Correct	4 ms	780 KB	correct
19	Correct	5 ms	780 KB	correct
20	Correct	4 ms	780 KB	correct
21	Correct	4 ms	828 KB	correct
22	Correct	4 ms	828 KB	correct
23	Correct	4 ms	828 KB	correct
24	Correct	5 ms	828 KB	correct
25	Correct	2 ms	828 KB	correct
26	Correct	3 ms	828 KB	correct
27	Correct	5 ms	828 KB	correct
28	Correct	4 ms	864 KB	correct
29	Correct	3 ms	864 KB	correct
30	Correct	4 ms	864 KB	correct
31	Correct	5 ms	864 KB	correct
32	Correct	4 ms	864 KB	correct
33	Correct	4 ms	864 KB	correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	correct
2	Correct	3 ms	488 KB	correct
3	Correct	2 ms	488 KB	correct
4	Correct	2 ms	488 KB	correct
5	Correct	3 ms	496 KB	correct
6	Correct	4 ms	496 KB	correct
7	Correct	2 ms	616 KB	correct
8	Correct	2 ms	736 KB	correct
9	Correct	2 ms	736 KB	correct
10	Correct	3 ms	736 KB	correct
11	Correct	3 ms	736 KB	correct
12	Correct	3 ms	736 KB	correct
13	Correct	3 ms	760 KB	correct
14	Correct	5 ms	760 KB	correct
15	Correct	6 ms	780 KB	correct
16	Correct	5 ms	780 KB	correct
17	Correct	4 ms	780 KB	correct
18	Correct	4 ms	780 KB	correct
19	Correct	5 ms	780 KB	correct
20	Correct	4 ms	780 KB	correct
21	Correct	4 ms	828 KB	correct
22	Correct	4 ms	828 KB	correct
23	Correct	4 ms	828 KB	correct
24	Correct	5 ms	828 KB	correct
25	Correct	2 ms	828 KB	correct
26	Correct	3 ms	828 KB	correct
27	Correct	5 ms	828 KB	correct
28	Correct	4 ms	864 KB	correct
29	Correct	3 ms	864 KB	correct
30	Correct	4 ms	864 KB	correct
31	Correct	5 ms	864 KB	correct
32	Correct	4 ms	864 KB	correct
33	Correct	4 ms	864 KB	correct
34	Correct	260 ms	1980 KB	correct
35	Correct	199 ms	2112 KB	correct
36	Correct	147 ms	2112 KB	correct
37	Correct	12 ms	2112 KB	correct
38	Correct	201 ms	2328 KB	correct
39	Correct	204 ms	2528 KB	correct
40	Correct	142 ms	2528 KB	correct
41	Correct	223 ms	2960 KB	correct
42	Correct	216 ms	3188 KB	correct
43	Correct	118 ms	3188 KB	correct
44	Correct	87 ms	3188 KB	correct
45	Correct	104 ms	3188 KB	correct
46	Correct	80 ms	3188 KB	correct
47	Correct	38 ms	3188 KB	correct
48	Correct	5 ms	3188 KB	correct
49	Correct	10 ms	3188 KB	correct
50	Correct	48 ms	3188 KB	correct
51	Correct	111 ms	3212 KB	correct
52	Correct	90 ms	3224 KB	correct
53	Correct	81 ms	3396 KB	correct
54	Correct	108 ms	3536 KB	correct
55	Correct	102 ms	3656 KB	correct
56	Correct	97 ms	3760 KB	correct
57	Correct	97 ms	3904 KB	correct

Subtask #4
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	3904 KB	correct
2	Correct	2 ms	3904 KB	correct
3	Incorrect	193 ms	6580 KB	WA in grader: NO
4	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	correct
2	Correct	3 ms	488 KB	correct
3	Correct	2 ms	488 KB	correct
4	Correct	2 ms	488 KB	correct
5	Correct	3 ms	496 KB	correct
6	Correct	4 ms	496 KB	correct
7	Correct	2 ms	616 KB	correct
8	Correct	2 ms	736 KB	correct
9	Correct	2 ms	736 KB	correct
10	Correct	3 ms	736 KB	correct
11	Correct	3 ms	736 KB	correct
12	Correct	3 ms	736 KB	correct
13	Correct	3 ms	760 KB	correct
14	Correct	5 ms	760 KB	correct
15	Correct	6 ms	780 KB	correct
16	Correct	5 ms	780 KB	correct
17	Correct	4 ms	780 KB	correct
18	Correct	4 ms	780 KB	correct
19	Correct	5 ms	780 KB	correct
20	Correct	4 ms	780 KB	correct
21	Correct	4 ms	828 KB	correct
22	Correct	4 ms	828 KB	correct
23	Correct	4 ms	828 KB	correct
24	Correct	5 ms	828 KB	correct
25	Correct	2 ms	828 KB	correct
26	Correct	3 ms	828 KB	correct
27	Correct	5 ms	828 KB	correct
28	Correct	4 ms	864 KB	correct
29	Correct	3 ms	864 KB	correct
30	Correct	4 ms	864 KB	correct
31	Correct	5 ms	864 KB	correct
32	Correct	4 ms	864 KB	correct
33	Correct	4 ms	864 KB	correct
34	Correct	260 ms	1980 KB	correct
35	Correct	199 ms	2112 KB	correct
36	Correct	147 ms	2112 KB	correct
37	Correct	12 ms	2112 KB	correct
38	Correct	201 ms	2328 KB	correct
39	Correct	204 ms	2528 KB	correct
40	Correct	142 ms	2528 KB	correct
41	Correct	223 ms	2960 KB	correct
42	Correct	216 ms	3188 KB	correct
43	Correct	118 ms	3188 KB	correct
44	Correct	87 ms	3188 KB	correct
45	Correct	104 ms	3188 KB	correct
46	Correct	80 ms	3188 KB	correct
47	Correct	38 ms	3188 KB	correct
48	Correct	5 ms	3188 KB	correct
49	Correct	10 ms	3188 KB	correct
50	Correct	48 ms	3188 KB	correct
51	Correct	111 ms	3212 KB	correct
52	Correct	90 ms	3224 KB	correct
53	Correct	81 ms	3396 KB	correct
54	Correct	108 ms	3536 KB	correct
55	Correct	102 ms	3656 KB	correct
56	Correct	97 ms	3760 KB	correct
57	Correct	97 ms	3904 KB	correct
58	Correct	3 ms	3904 KB	correct
59	Correct	2 ms	3904 KB	correct
60	Incorrect	193 ms	6580 KB	WA in grader: NO
61	Halted	0 ms	0 KB	-

답안 #69929

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 17.0 / 17.0

Subtask #3 21.0 / 21.0

Subtask #4 0 / 19.0

Subtask #5 0 / 30.0

Subtask #1
13.0 / 13.0

Subtask #2
17.0 / 17.0

Subtask #3
21.0 / 21.0

Subtask #4
0 / 19.0

Subtask #5
0 / 30.0