oj.uz

Submission #69929

# Submission time Handle Problem Language Result Execution time Memory
69929 2018-08-22T04:14:59 Z top34051 Simurgh (IOI17_simurgh) C++17
51 / 100
 260 ms 6580 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -