oj.uz

Submission #51013

# Submission time Handle Problem Language Result Execution time Memory
51013 2018-06-15T15:21:28 Z FLDutchman Simurgh (IOI17_simurgh) C++14
100 / 100
 318 ms 30336 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, l, r) for(int i = l; i < r; i++)
#define pb push_back
#define fst first
#define snd second

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

vi isGolden; // -1 = unknown; 0 = false; 1 = true
vi par, parEdge, height; //Parent in dfs tree
vi tree; // set of edges
vi adj[510];
vi adjidx[510];
vii edges; //Edges: sorted by heigth in tree


void buildTree(int n){
	FOR(i, 0, adj[n].size()){
		int k = adj[n][i];
		if(height[k] == -1){
			par[k] = n;
			parEdge[k] = adjidx[n][i];
			tree.pb(parEdge[k]);
			height[k] = height[n]+1;
			buildTree(k);
		}
	}
}

int queryReplacement(int a, int b){
	FOR(i, 0, tree.size()){
		if(tree[i] == a) {
			tree[i] = b;
			int k = count_common_roads(tree);
			tree[i] = a;
			return k;
		}
	}
}

void detTree(){
	int treecnt = count_common_roads(tree);
	FOR(i, 0, edges.size()){
		auto e = edges[i];
		if(par[e.fst] == e.snd) continue;
		int n = e.fst;
		bool allDet = true, allUndet = true;
		int p = 0;
		while(n != e.snd){
			if(isGolden[parEdge[n]] == -1) allDet = false;
			if(isGolden[parEdge[n]] != -1) { p = parEdge[n]; allUndet = false; }
			n = par[n];
		}


		if(allDet) {
			continue;
		}
		
		n = e.fst;	
		if(allUndet){
			bool dec = false, inc = false;
			while(n != e.snd){
				int q = queryReplacement(parEdge[n], i);
				if(q < treecnt) {dec = true; isGolden[parEdge[n]] = 1;}
				if(q > treecnt) {inc = true; isGolden[parEdge[n]] = 0;}
				n = par[n];
			}
			n = e.fst;
			if(inc) while(n != e.snd) {if(isGolden[parEdge[n]] == -1) isGolden[parEdge[n]] = 1; n = par[n];} 
			else if(dec) while(n != e.snd) {if(isGolden[parEdge[n]] == -1) isGolden[parEdge[n]] = 0; n = par[n];}
			else while(n != e.snd) {isGolden[parEdge[n]] = 0; n = par[n];} 
		} else {
			int k = queryReplacement(p, i);
			int v = k - treecnt + isGolden[p];
			while(n != e.snd){
				if(isGolden[parEdge[n]] == -1){
					int t = queryReplacement(parEdge[n], i);
					isGolden[parEdge[n]] = treecnt + v - t;
				}
				n = par[n];
			}
		}
	}

	for(int e : tree){
		if(isGolden[e] == -1) isGolden[e] = 1;
	}
}
vi ufp;

int find(int a) {return ufp[a] = ufp[a] == a ? a : find(ufp[a]);}
void comb(int a, int b) {ufp[find(a)] = ufp[find(b)];}

int queryForest(vi forest){
	ufp.clear();
	FOR(i, 0, tree.size()+1) ufp.pb(i);
	for(int e : forest){
		comb(edges[e].fst, edges[e].snd);
	}
	int treeVal = 0;
	for(int e : tree){
		if(find(edges[e].fst) != find(edges[e].snd)){
			treeVal += isGolden[e];
			forest.pb(e);
			comb(edges[e].fst, edges[e].snd);
		}
	}

	return count_common_roads(forest) - treeVal;
}

int queryInterval(int n, int lb, int rb){
	vi forest;
	FOR(i, lb, rb){
		if(isGolden[adjidx[n][i]] != 1) forest.pb(adjidx[n][i]);
	}
	return queryForest(forest);
}


vi find_roads(int n, vi u, vi v) {
	par.assign(n, -1); parEdge.assign(n, -1); height.assign(n, -1);
	isGolden.assign(u.size(), -1);
	FOR(i, 0, u.size()) {
		adj[u[i]].pb(v[i]);
		adj[v[i]].pb(u[i]);
		adjidx[u[i]].pb(i);
		adjidx[v[i]].pb(i);
	}
	par[0] = height[0] = 0;
	parEdge[0] = -1;
	buildTree(0);
	FOR(i, 0, u.size()) {
		if(height[u[i]] > height[v[i]]) edges.pb({u[i], v[i]});
		else edges.pb({v[i], u[i]});
	}
	
	detTree();
	queue<int> q;
	vi outCount;
	FOR(i, 0, tree.size()+1){
		outCount.pb(queryInterval(i, 0, adj[i].size()));
		if(outCount[i] == 1) q.push(i);
	}
	int c = 0;
	while(!q.empty()){
		int k = q.front(); q.pop();
		if(outCount[k] == 0) continue;
		int lb = 0, rb = adj[k].size();
		while(lb+1 != rb){
			int mb = (lb+rb)/2;
			if(queryInterval(k, lb, mb)) rb = mb;
			else lb = mb;
		}
		isGolden[adjidx[k][lb]] = 1;
		outCount[adj[k][lb]] --;
		outCount[k]--;
		if(outCount[adj[k][lb]] == 1) { q.push(adj[k][lb]);}
	}

	vi t;
	FOR(i, 0, isGolden.size()){
		if(isGolden[i] == 1) t.pb(i);
	}

	
	return t;
}

Compilation message

simurgh.cpp: In function 'void buildTree(int)':
simurgh.cpp:5:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = l; i < r; i++)
simurgh.cpp:23:6:
  FOR(i, 0, adj[n].size()){
      ~~~~~~~~~~~~~~~~~~~               
simurgh.cpp:23:2: note: in expansion of macro 'FOR'
  FOR(i, 0, adj[n].size()){
  ^~~
simurgh.cpp: In function 'int queryReplacement(int, int)':
simurgh.cpp:5:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = l; i < r; i++)
simurgh.cpp:36:6:
  FOR(i, 0, tree.size()){
      ~~~~~~~~~~~~~~~~~                 
simurgh.cpp:36:2: note: in expansion of macro 'FOR'
  FOR(i, 0, tree.size()){
  ^~~
simurgh.cpp: In function 'void detTree()':
simurgh.cpp:5:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = l; i < r; i++)
simurgh.cpp:48:6:
  FOR(i, 0, edges.size()){
      ~~~~~~~~~~~~~~~~~~                
simurgh.cpp:48:2: note: in expansion of macro 'FOR'
  FOR(i, 0, edges.size()){
  ^~~
simurgh.cpp: In function 'int queryForest(vi)':
simurgh.cpp:5:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = l; i < r; i++)
simurgh.cpp:102:6:
  FOR(i, 0, tree.size()+1) ufp.pb(i);
      ~~~~~~~~~~~~~~~~~~~               
simurgh.cpp:102:2: note: in expansion of macro 'FOR'
  FOR(i, 0, tree.size()+1) ufp.pb(i);
  ^~~
simurgh.cpp: In function 'vi find_roads(int, vi, vi)':
simurgh.cpp:5:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = l; i < r; i++)
simurgh.cpp:130:6:
  FOR(i, 0, u.size()) {
      ~~~~~~~~~~~~~~                    
simurgh.cpp:130:2: note: in expansion of macro 'FOR'
  FOR(i, 0, u.size()) {
  ^~~
simurgh.cpp:5:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = l; i < r; i++)
simurgh.cpp:139:6:
  FOR(i, 0, u.size()) {
      ~~~~~~~~~~~~~~                    
simurgh.cpp:139:2: note: in expansion of macro 'FOR'
  FOR(i, 0, u.size()) {
  ^~~
simurgh.cpp:5:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = l; i < r; i++)
simurgh.cpp:147:6:
  FOR(i, 0, tree.size()+1){
      ~~~~~~~~~~~~~~~~~~~               
simurgh.cpp:147:2: note: in expansion of macro 'FOR'
  FOR(i, 0, tree.size()+1){
  ^~~
simurgh.cpp:5:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = l; i < r; i++)
simurgh.cpp:168:6:
  FOR(i, 0, isGolden.size()){
      ~~~~~~~~~~~~~~~~~~~~~             
simurgh.cpp:168:2: note: in expansion of macro 'FOR'
  FOR(i, 0, isGolden.size()){
  ^~~
simurgh.cpp:151:6: warning: unused variable 'c' [-Wunused-variable]
  int c = 0;
      ^
simurgh.cpp: In function 'int queryReplacement(int, int)':
simurgh.cpp:44:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 428 KB correct
4 Correct 2 ms 536 KB correct
5 Correct 2 ms 580 KB correct
6 Correct 2 ms 580 KB correct
7 Correct 2 ms 616 KB correct
8 Correct 2 ms 616 KB correct
9 Correct 2 ms 616 KB correct
10 Correct 2 ms 616 KB correct
11 Correct 2 ms 616 KB correct
12 Correct 2 ms 616 KB correct
13 Correct 2 ms 616 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 428 KB correct
4 Correct 2 ms 536 KB correct
5 Correct 2 ms 580 KB correct
6 Correct 2 ms 580 KB correct
7 Correct 2 ms 616 KB correct
8 Correct 2 ms 616 KB correct
9 Correct 2 ms 616 KB correct
10 Correct 2 ms 616 KB correct
11 Correct 2 ms 616 KB correct
12 Correct 2 ms 616 KB correct
13 Correct 2 ms 616 KB correct
14 Correct 4 ms 736 KB correct
15 Correct 4 ms 736 KB correct
16 Correct 4 ms 736 KB correct
17 Correct 4 ms 736 KB correct
18 Correct 3 ms 736 KB correct
19 Correct 4 ms 736 KB correct
20 Correct 3 ms 736 KB correct
21 Correct 4 ms 736 KB correct
22 Correct 3 ms 736 KB correct
23 Correct 3 ms 736 KB correct
24 Correct 3 ms 736 KB correct
25 Correct 3 ms 736 KB correct
26 Correct 3 ms 736 KB correct
27 Correct 3 ms 736 KB correct
28 Correct 3 ms 736 KB correct
29 Correct 3 ms 736 KB correct
30 Correct 3 ms 736 KB correct
31 Correct 3 ms 736 KB correct
32 Correct 4 ms 736 KB correct
33 Correct 3 ms 736 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 428 KB correct
4 Correct 2 ms 536 KB correct
5 Correct 2 ms 580 KB correct
6 Correct 2 ms 580 KB correct
7 Correct 2 ms 616 KB correct
8 Correct 2 ms 616 KB correct
9 Correct 2 ms 616 KB correct
10 Correct 2 ms 616 KB correct
11 Correct 2 ms 616 KB correct
12 Correct 2 ms 616 KB correct
13 Correct 2 ms 616 KB correct
14 Correct 4 ms 736 KB correct
15 Correct 4 ms 736 KB correct
16 Correct 4 ms 736 KB correct
17 Correct 4 ms 736 KB correct
18 Correct 3 ms 736 KB correct
19 Correct 4 ms 736 KB correct
20 Correct 3 ms 736 KB correct
21 Correct 4 ms 736 KB correct
22 Correct 3 ms 736 KB correct
23 Correct 3 ms 736 KB correct
24 Correct 3 ms 736 KB correct
25 Correct 3 ms 736 KB correct
26 Correct 3 ms 736 KB correct
27 Correct 3 ms 736 KB correct
28 Correct 3 ms 736 KB correct
29 Correct 3 ms 736 KB correct
30 Correct 3 ms 736 KB correct
31 Correct 3 ms 736 KB correct
32 Correct 4 ms 736 KB correct
33 Correct 3 ms 736 KB correct
34 Correct 58 ms 2020 KB correct
35 Correct 48 ms 2232 KB correct
36 Correct 38 ms 2232 KB correct
37 Correct 12 ms 2232 KB correct
38 Correct 46 ms 2684 KB correct
39 Correct 43 ms 2804 KB correct
40 Correct 38 ms 2848 KB correct
41 Correct 46 ms 3276 KB correct
42 Correct 49 ms 3444 KB correct
43 Correct 21 ms 3444 KB correct
44 Correct 21 ms 3444 KB correct
45 Correct 20 ms 3444 KB correct
46 Correct 19 ms 3444 KB correct
47 Correct 13 ms 3444 KB correct
48 Correct 6 ms 3444 KB correct
49 Correct 9 ms 3444 KB correct
50 Correct 16 ms 3444 KB correct
51 Correct 21 ms 3444 KB correct
52 Correct 19 ms 3444 KB correct
53 Correct 17 ms 3444 KB correct
54 Correct 22 ms 3744 KB correct
55 Correct 21 ms 3744 KB correct
56 Correct 21 ms 3892 KB correct
57 Correct 20 ms 4076 KB correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4076 KB correct
2 Correct 2 ms 4076 KB correct
3 Correct 207 ms 7668 KB correct
4 Correct 287 ms 10064 KB correct
5 Correct 257 ms 10992 KB correct
6 Correct 318 ms 11792 KB correct
7 Correct 289 ms 12756 KB correct
8 Correct 300 ms 13712 KB correct
9 Correct 309 ms 14624 KB correct
10 Correct 307 ms 15500 KB correct
11 Correct 294 ms 16476 KB correct
12 Correct 260 ms 17400 KB correct
13 Correct 2 ms 17400 KB correct
14 Correct 292 ms 18320 KB correct
15 Correct 254 ms 19276 KB correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 428 KB correct
4 Correct 2 ms 536 KB correct
5 Correct 2 ms 580 KB correct
6 Correct 2 ms 580 KB correct
7 Correct 2 ms 616 KB correct
8 Correct 2 ms 616 KB correct
9 Correct 2 ms 616 KB correct
10 Correct 2 ms 616 KB correct
11 Correct 2 ms 616 KB correct
12 Correct 2 ms 616 KB correct
13 Correct 2 ms 616 KB correct
14 Correct 4 ms 736 KB correct
15 Correct 4 ms 736 KB correct
16 Correct 4 ms 736 KB correct
17 Correct 4 ms 736 KB correct
18 Correct 3 ms 736 KB correct
19 Correct 4 ms 736 KB correct
20 Correct 3 ms 736 KB correct
21 Correct 4 ms 736 KB correct
22 Correct 3 ms 736 KB correct
23 Correct 3 ms 736 KB correct
24 Correct 3 ms 736 KB correct
25 Correct 3 ms 736 KB correct
26 Correct 3 ms 736 KB correct
27 Correct 3 ms 736 KB correct
28 Correct 3 ms 736 KB correct
29 Correct 3 ms 736 KB correct
30 Correct 3 ms 736 KB correct
31 Correct 3 ms 736 KB correct
32 Correct 4 ms 736 KB correct
33 Correct 3 ms 736 KB correct
34 Correct 58 ms 2020 KB correct
35 Correct 48 ms 2232 KB correct
36 Correct 38 ms 2232 KB correct
37 Correct 12 ms 2232 KB correct
38 Correct 46 ms 2684 KB correct
39 Correct 43 ms 2804 KB correct
40 Correct 38 ms 2848 KB correct
41 Correct 46 ms 3276 KB correct
42 Correct 49 ms 3444 KB correct
43 Correct 21 ms 3444 KB correct
44 Correct 21 ms 3444 KB correct
45 Correct 20 ms 3444 KB correct
46 Correct 19 ms 3444 KB correct
47 Correct 13 ms 3444 KB correct
48 Correct 6 ms 3444 KB correct
49 Correct 9 ms 3444 KB correct
50 Correct 16 ms 3444 KB correct
51 Correct 21 ms 3444 KB correct
52 Correct 19 ms 3444 KB correct
53 Correct 17 ms 3444 KB correct
54 Correct 22 ms 3744 KB correct
55 Correct 21 ms 3744 KB correct
56 Correct 21 ms 3892 KB correct
57 Correct 20 ms 4076 KB correct
58 Correct 2 ms 4076 KB correct
59 Correct 2 ms 4076 KB correct
60 Correct 207 ms 7668 KB correct
61 Correct 287 ms 10064 KB correct
62 Correct 257 ms 10992 KB correct
63 Correct 318 ms 11792 KB correct
64 Correct 289 ms 12756 KB correct
65 Correct 300 ms 13712 KB correct
66 Correct 309 ms 14624 KB correct
67 Correct 307 ms 15500 KB correct
68 Correct 294 ms 16476 KB correct
69 Correct 260 ms 17400 KB correct
70 Correct 2 ms 17400 KB correct
71 Correct 292 ms 18320 KB correct
72 Correct 254 ms 19276 KB correct
73 Correct 2 ms 19276 KB correct
74 Correct 246 ms 20180 KB correct
75 Correct 278 ms 21024 KB correct
76 Correct 112 ms 21024 KB correct
77 Correct 274 ms 22312 KB correct
78 Correct 250 ms 23308 KB correct
79 Correct 272 ms 24232 KB correct
80 Correct 255 ms 25028 KB correct
81 Correct 225 ms 25412 KB correct
82 Correct 241 ms 26684 KB correct
83 Correct 171 ms 26684 KB correct
84 Correct 107 ms 26684 KB correct
85 Correct 102 ms 26684 KB correct
86 Correct 74 ms 26684 KB correct
87 Correct 66 ms 26684 KB correct
88 Correct 60 ms 26684 KB correct
89 Correct 56 ms 26684 KB correct
90 Correct 53 ms 26684 KB correct
91 Correct 27 ms 26684 KB correct
92 Correct 19 ms 26684 KB correct
93 Correct 129 ms 27740 KB correct
94 Correct 76 ms 27740 KB correct
95 Correct 74 ms 27740 KB correct
96 Correct 61 ms 27740 KB correct
97 Correct 61 ms 27740 KB correct
98 Correct 62 ms 27740 KB correct
99 Correct 54 ms 27740 KB correct
100 Correct 34 ms 27740 KB correct
101 Correct 21 ms 27740 KB correct
102 Correct 102 ms 28940 KB correct
103 Correct 103 ms 29544 KB correct
104 Correct 103 ms 29872 KB correct
105 Correct 100 ms 30336 KB correct