답안 #51013 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51013	2018-06-15T15:21:28 Z	FLDutchman	Simurgh (IOI17_simurgh)	C++14	100 / 100	318 ms	30336 KB

simurgh

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #51013

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 17.0 / 17.0

Subtask #3 21.0 / 21.0

Subtask #4 19.0 / 19.0

Subtask #5 30.0 / 30.0

Subtask #1
13.0 / 13.0

Subtask #2
17.0 / 17.0

Subtask #3
21.0 / 21.0

Subtask #4
19.0 / 19.0

Subtask #5
30.0 / 30.0