oj.uz

Submission #340943

# Submission time Handle Problem Language Result Execution time Memory
340943 2020-12-28T15:05:35 Z pggp Simurgh (IOI17_simurgh) C++14
51 / 100
 207 ms 6252 KB 
#include <bits/stdc++.h>
#include "simurgh.h"

using namespace std;


int k[30000];

vector < int > E[30000];
vector < int > E_id[30000];
bool used[30000];
int parent[30000];
int parent_road[30000];
int depth[30000];

vector < int > u_back, v_back;
vector < int > id;

vector < int > tree;

void dfs(int vertex){
	//outcout << vertex << endl;
	used[vertex] = true;
	for(int i = 0; i < E[vertex].size(); i++){
		int v = E[vertex][i];
		if(!used[v]){
			parent[v] = vertex;
			parent_road[v] = E_id[vertex][i];
			tree.push_back(parent_road[v]);

			//cout << vertex << " to " << v << endl;
			depth[v] = depth[vertex] + 1;
			dfs(v);
		}
		else if (v != parent[vertex] and depth[v] < depth[vertex]){
			v_back.push_back(vertex);
			u_back.push_back(v);
			id.push_back(E_id[vertex][i]);
		}
	}
}


vector < int > find_roads(int n, vector < int > u, vector < int > v){

	int m = u.size();
	for (int i = 0; i < m; ++i)
	{
		k[i] = -1;
	}

	for (int i = 0; i < m; ++i)
	{
		E[u[i]].push_back(v[i]);
		E_id[u[i]].push_back(i);
		E[v[i]].push_back(u[i]);
		E_id[v[i]].push_back(i);
	}
	parent[0] = -1;
	dfs(0);

	int tr = count_common_roads(tree);

	// tutaj zaczyna się zabawa z cyklami
	for(int i = 0; i < v_back.size(); i++){
		vector < int > cycle;
		cycle.push_back(id[i]);
		int cur = v_back[i];
		//cout << v_back[i] << " " << u_back[i] << endl;
		while(cur != u_back[i]){
			cycle.push_back(parent_road[cur]);
			cur = parent[cur];
		}
		vector < int > an;

		int minim = 100000;
		int maxim = 0;

		int sample_k, sample_result;
		bool sampled = false;

		for(int t : cycle){
			if(t == id[i]){
				//cout << t << " - " << tr << endl;
				an.push_back(tr);
				minim = min(minim, tr);
				maxim = max(maxim, tr);
				continue;
			}
			if(k[t] != -1 and sampled){
				//cout << "OK" << endl;
				an.push_back(0);
				continue;
			}
			if(k[t] != -1 and !sampled){
				//cout << "t = " << t  << " k[" << t << "] = " << k[t] << endl;
				sample_k = k[t];
				sampled = true;
			}
			//cout << "t = " << t << endl;
			vector < int > to_q;
			// drzewo z cyklem bez t
			for(int e : tree){
				if(e != t){
					to_q.push_back(e);
				}
			}
			to_q.push_back(id[i]);

			/*if(t == 129){
				cout << "zz" << endl;
				for(int d : to_q){
					cout << d << " ";
				}
				cout << endl;
			}*/
			int resp = count_common_roads(to_q);
			an.push_back(resp);

			//if(t == 129){
			//	cout << "resp = " <<  resp << endl;
			//}
			//cout << t << " resp = " << resp << endl;
			minim = min(minim, resp);
			maxim = max(maxim, resp);
			if(k[t] != -1){
				sample_result = resp;
				sampled = true;
			}
		}

		if(maxim == minim and (!sampled or (sample_k == 0))){
			for(int e : cycle){
				if(k[e] == -1)	k[e] = 0;
				//cout << "e = " <<  e << " sampled = " << sampled << " sample_k = " << sample_k << endl;
			}
		}
		if(maxim == minim and sampled and sample_k == 1){
			for(int e : cycle){
				//cout << "E = " << e << endl;
				if(k[e] == -1)	k[e] = 1;
			}
		}

		//if(maxim > minim){
			for (int j = 0; j < an.size(); ++j)
			{
				if(an[j] == maxim){
					//cout << "k["  << cycle[j] << "] = " << 0 << endl;
					if(k[cycle[j]] == -1)	k[cycle[j]] = 0;

				}
				else{
					//cout << "k["  << cycle[j] << "] = " << 1 << endl;
					if(k[cycle[j]] == -1)	k[cycle[j]] = 1;
					if(cycle[j] == 129){
						//cout << "XXX" << an[j] << " " << minim << endl;
					}
				}
			}
		//}

		


//		cout << endl;
	}


	vector < int > ans;
	for (int i = 0; i < m; ++i)
	{
		if(k[i] == 1 or k[i] == -1){
			ans.push_back(i);
		}
	}
	return ans;
}

Compilation message

simurgh.cpp: In function 'void dfs(int)':
simurgh.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(int i = 0; i < E[vertex].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i = 0; i < v_back.size(); i++){
      |                 ~~^~~~~~~~~~~~~~~
simurgh.cpp:146:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |    for (int j = 0; j < an.size(); ++j)
      |                    ~~^~~~~~~~~~~
simurgh.cpp:79:17: warning: variable 'sample_result' set but not used [-Wunused-but-set-variable]
   79 |   int sample_k, sample_result;
      |                 ^~~~~~~~~~~~~
simurgh.cpp:79:7: warning: 'sample_k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |   int sample_k, sample_result;
      |       ^~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1772 KB correct
2 Correct 1 ms 1772 KB correct
3 Correct 1 ms 1772 KB correct
4 Correct 2 ms 1772 KB correct
5 Correct 1 ms 1772 KB correct
6 Correct 1 ms 1772 KB correct
7 Correct 1 ms 1772 KB correct
8 Correct 1 ms 1772 KB correct
9 Correct 1 ms 1772 KB correct
10 Correct 2 ms 1772 KB correct
11 Correct 2 ms 1920 KB correct
12 Correct 1 ms 1772 KB correct
13 Correct 1 ms 1784 KB correct

Subtask #2
17.0 / 17.0

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

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1772 KB correct
2 Correct 1 ms 1772 KB correct
3 Correct 1 ms 1772 KB correct
4 Correct 2 ms 1772 KB correct
5 Correct 1 ms 1772 KB correct
6 Correct 1 ms 1772 KB correct
7 Correct 1 ms 1772 KB correct
8 Correct 1 ms 1772 KB correct
9 Correct 1 ms 1772 KB correct
10 Correct 2 ms 1772 KB correct
11 Correct 2 ms 1920 KB correct
12 Correct 1 ms 1772 KB correct
13 Correct 1 ms 1784 KB correct
14 Correct 4 ms 1772 KB correct
15 Correct 4 ms 1772 KB correct
16 Correct 4 ms 1772 KB correct
17 Correct 4 ms 1772 KB correct
18 Correct 2 ms 1772 KB correct
19 Correct 4 ms 1772 KB correct
20 Correct 4 ms 1772 KB correct
21 Correct 4 ms 1772 KB correct
22 Correct 3 ms 1772 KB correct
23 Correct 3 ms 1772 KB correct
24 Correct 3 ms 1772 KB correct
25 Correct 2 ms 1772 KB correct
26 Correct 3 ms 1792 KB correct
27 Correct 3 ms 1772 KB correct
28 Correct 2 ms 1772 KB correct
29 Correct 2 ms 1772 KB correct
30 Correct 4 ms 1772 KB correct
31 Correct 3 ms 1772 KB correct
32 Correct 3 ms 1772 KB correct
33 Correct 3 ms 1772 KB correct
34 Correct 201 ms 3628 KB correct
35 Correct 198 ms 3688 KB correct
36 Correct 137 ms 3180 KB correct
37 Correct 10 ms 1900 KB correct
38 Correct 207 ms 3560 KB correct
39 Correct 177 ms 3432 KB correct
40 Correct 138 ms 3436 KB correct
41 Correct 204 ms 3692 KB correct
42 Correct 195 ms 3560 KB correct
43 Correct 104 ms 3052 KB correct
44 Correct 83 ms 2668 KB correct
45 Correct 96 ms 2668 KB correct
46 Correct 73 ms 2540 KB correct
47 Correct 32 ms 2156 KB correct
48 Correct 4 ms 1772 KB correct
49 Correct 10 ms 1900 KB correct
50 Correct 31 ms 2176 KB correct
51 Correct 107 ms 2688 KB correct
52 Correct 81 ms 2668 KB correct
53 Correct 71 ms 2540 KB correct
54 Correct 104 ms 3052 KB correct
55 Correct 98 ms 2796 KB correct
56 Correct 100 ms 2688 KB correct
57 Correct 99 ms 2668 KB correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1772 KB correct
2 Correct 1 ms 1772 KB correct
3 Runtime error 23 ms 6252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1772 KB correct
2 Correct 1 ms 1772 KB correct
3 Correct 1 ms 1772 KB correct
4 Correct 2 ms 1772 KB correct
5 Correct 1 ms 1772 KB correct
6 Correct 1 ms 1772 KB correct
7 Correct 1 ms 1772 KB correct
8 Correct 1 ms 1772 KB correct
9 Correct 1 ms 1772 KB correct
10 Correct 2 ms 1772 KB correct
11 Correct 2 ms 1920 KB correct
12 Correct 1 ms 1772 KB correct
13 Correct 1 ms 1784 KB correct
14 Correct 4 ms 1772 KB correct
15 Correct 4 ms 1772 KB correct
16 Correct 4 ms 1772 KB correct
17 Correct 4 ms 1772 KB correct
18 Correct 2 ms 1772 KB correct
19 Correct 4 ms 1772 KB correct
20 Correct 4 ms 1772 KB correct
21 Correct 4 ms 1772 KB correct
22 Correct 3 ms 1772 KB correct
23 Correct 3 ms 1772 KB correct
24 Correct 3 ms 1772 KB correct
25 Correct 2 ms 1772 KB correct
26 Correct 3 ms 1792 KB correct
27 Correct 3 ms 1772 KB correct
28 Correct 2 ms 1772 KB correct
29 Correct 2 ms 1772 KB correct
30 Correct 4 ms 1772 KB correct
31 Correct 3 ms 1772 KB correct
32 Correct 3 ms 1772 KB correct
33 Correct 3 ms 1772 KB correct
34 Correct 201 ms 3628 KB correct
35 Correct 198 ms 3688 KB correct
36 Correct 137 ms 3180 KB correct
37 Correct 10 ms 1900 KB correct
38 Correct 207 ms 3560 KB correct
39 Correct 177 ms 3432 KB correct
40 Correct 138 ms 3436 KB correct
41 Correct 204 ms 3692 KB correct
42 Correct 195 ms 3560 KB correct
43 Correct 104 ms 3052 KB correct
44 Correct 83 ms 2668 KB correct
45 Correct 96 ms 2668 KB correct
46 Correct 73 ms 2540 KB correct
47 Correct 32 ms 2156 KB correct
48 Correct 4 ms 1772 KB correct
49 Correct 10 ms 1900 KB correct
50 Correct 31 ms 2176 KB correct
51 Correct 107 ms 2688 KB correct
52 Correct 81 ms 2668 KB correct
53 Correct 71 ms 2540 KB correct
54 Correct 104 ms 3052 KB correct
55 Correct 98 ms 2796 KB correct
56 Correct 100 ms 2688 KB correct
57 Correct 99 ms 2668 KB correct
58 Correct 2 ms 1772 KB correct
59 Correct 1 ms 1772 KB correct
60 Runtime error 23 ms 6252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
61 Halted 0 ms 0 KB -