oj.uz

Submission #407412

# Submission time Handle Problem Language Result Execution time Memory
407412 2021-05-18T22:17:41 Z peuch Simurgh (IOI17_simurgh) C++17
30 / 100
 197 ms 4092 KB 
#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1010;

int n, m;
vector<int> u, v;

vector<int> ar[MAXN], id[MAXN];
int marc[MAXN], pai[MAXN], paiID[MAXN], prof[MAXN];
int grp[200000];
int pode[200000];
int cnt[200000];

int a;

int rep[MAXN], tam[MAXN];

vector<int> getPath(int a, int b);
vector<int> getST(vector<int> base);
bool uni(int a, int b);
int find(int a);
void dfs(int cur);

vector<int> find_roads(int _n, vector<int> _u, vector<int> _v) {
	n = _n;
	u = _u, v = _v;
	m = u.size();
	
	for(int i = 0; i < u.size(); i++){
		ar[u[i]].push_back(v[i]);
		id[u[i]].push_back(i);
		ar[v[i]].push_back(u[i]);
		id[v[i]].push_back(i);
	}
	
	vector<int> nulo;
	vector<int> tree = getST(nulo);
	
	a = count_common_roads(tree);
	
	for(int i = 0; i < tree.size(); i++)
		pode[tree[i]] = 1;
	
	dfs(0);
	
	for(int i = 0; i < m; i++){
		if(grp[i] != 0 || pode[i]) continue;
		vector<int> path = getPath(u[i], v[i]);
		
		int maxi = 0;
		bool flag = false;
		tree.push_back(i);
		path.push_back(i);
		cnt[i] = a;
		for(int j = 0; j < path.size(); j++){
			if(grp[path[j]] != 0){
				if(flag) continue;
				if(grp[path[j]] == 1) continue;
				flag = true;
			}
			
			vector<int> test;
			for(int k = 0; k < tree.size(); k++)
				if(tree[k] != path[j]) test.push_back(tree[k]);
			
			cnt[path[j]] = count_common_roads(test);
			maxi = max(maxi, cnt[path[j]]);
		}	
		tree.pop_back();
		
		for(int j = 0; j < path.size(); j++){
			if(grp[path[j]] != 0) continue;
			if(cnt[path[j]] == maxi) grp[path[j]] = -1;
			if(cnt[path[j]] != maxi) grp[path[j]] = 1;
//			printf("Cnt[%d] = %d -> grp = %d\n", path[j], cnt[path[j]], grp[path[j]]);
		}
		 
	}
	
	vector<int> ans;
	for(int i = 0; i < m; i++)
		if(grp[i] != -1) ans.push_back(i);
		
//	for(int i = 0; i < ans.size(); i++){
//		printf("%d ", ans[i]);
//	}
//	printf("\n");
	
	return ans;
}

vector<int> getPath(int a, int b){
	vector<int> ret;
	if(prof[a] < prof[b]) swap(a, b);
	while(prof[a] > prof[b]){
		ret.push_back(paiID[a]);
		a = pai[a];
	}
	while(a != b){
		ret.push_back(paiID[a]);
		a = pai[a];
		ret.push_back(paiID[b]);
		b = pai[b];
	}
	return ret;
}

vector<int> getST(vector<int> base){
	vector<int> ret;
	for(int i = 0; i < n; i++){
		tam[i] = 1;
		rep[i] = i;
	}
	for(int i = 0; i < base.size(); i++)
		uni(u[base[i]], v[base[i]]);
	for(int i = 0; i < m; i++)
		if(uni(u[i], v[i])) ret.push_back(i);
	return ret;
}

bool uni(int a, int b){
	a = find(a);
	b = find(b);
	if(a == b) return 0;
	if(tam[a] < tam[b]) swap(a, b);
	tam[a] += tam[b];
	rep[b] = a;
	return 1;
}

int find(int a){
	if(a == rep[a]) return a;
	return rep[a] = find(rep[a]);
}

void dfs(int cur){
	for(int i = 0; i < ar[cur].size(); i++){
		int viz = ar[cur][i];
		if(!pode[id[cur][i]]) continue;
		if(viz == pai[cur]) continue;
		pai[viz] = cur;
		paiID[viz] = id[cur][i];
		prof[viz] = prof[cur] + 1;
		dfs(viz);
	}
}
/*
5 7
0 1
1 2
2 3
3 4
0 2
1 3
4 2
1 3 4 6
*/

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i = 0; i < u.size(); i++){
      |                 ~~^~~~~~~~~~
simurgh.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(int i = 0; i < tree.size(); i++)
      |                 ~~^~~~~~~~~~~~~
simurgh.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for(int j = 0; j < path.size(); j++){
      |                  ~~^~~~~~~~~~~~~
simurgh.cpp:65:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |    for(int k = 0; k < tree.size(); k++)
      |                   ~~^~~~~~~~~~~~~
simurgh.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for(int j = 0; j < path.size(); j++){
      |                  ~~^~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> getST(std::vector<int>)':
simurgh.cpp:116:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |  for(int i = 0; i < base.size(); i++)
      |                 ~~^~~~~~~~~~~~~
simurgh.cpp: In function 'void dfs(int)':
simurgh.cpp:139:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |  for(int i = 0; i < ar[cur].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 332 KB correct
3 Correct 1 ms 332 KB correct
4 Correct 1 ms 332 KB correct
5 Correct 1 ms 332 KB correct
6 Correct 1 ms 332 KB correct
7 Correct 1 ms 332 KB correct
8 Correct 1 ms 332 KB correct
9 Correct 1 ms 332 KB correct
10 Correct 1 ms 332 KB correct
11 Correct 1 ms 332 KB correct
12 Correct 1 ms 332 KB correct
13 Correct 1 ms 332 KB correct
14 Correct 5 ms 448 KB correct
15 Correct 5 ms 448 KB correct
16 Correct 5 ms 332 KB correct
17 Correct 4 ms 332 KB correct
18 Correct 2 ms 332 KB correct
19 Correct 4 ms 332 KB correct
20 Correct 4 ms 332 KB correct
21 Correct 4 ms 332 KB correct
22 Correct 2 ms 332 KB correct
23 Correct 2 ms 332 KB correct
24 Correct 2 ms 332 KB correct
25 Correct 1 ms 332 KB correct
26 Correct 2 ms 332 KB correct
27 Correct 2 ms 332 KB correct
28 Correct 1 ms 332 KB correct
29 Correct 1 ms 332 KB correct
30 Correct 2 ms 332 KB correct
31 Correct 2 ms 332 KB correct
32 Correct 2 ms 332 KB correct
33 Correct 2 ms 332 KB correct
34 Incorrect 197 ms 1620 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 332 KB correct
3 Incorrect 150 ms 4092 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 332 KB correct
3 Correct 1 ms 332 KB correct
4 Correct 1 ms 332 KB correct
5 Correct 1 ms 332 KB correct
6 Correct 1 ms 332 KB correct
7 Correct 1 ms 332 KB correct
8 Correct 1 ms 332 KB correct
9 Correct 1 ms 332 KB correct
10 Correct 1 ms 332 KB correct
11 Correct 1 ms 332 KB correct
12 Correct 1 ms 332 KB correct
13 Correct 1 ms 332 KB correct
14 Correct 5 ms 448 KB correct
15 Correct 5 ms 448 KB correct
16 Correct 5 ms 332 KB correct
17 Correct 4 ms 332 KB correct
18 Correct 2 ms 332 KB correct
19 Correct 4 ms 332 KB correct
20 Correct 4 ms 332 KB correct
21 Correct 4 ms 332 KB correct
22 Correct 2 ms 332 KB correct
23 Correct 2 ms 332 KB correct
24 Correct 2 ms 332 KB correct
25 Correct 1 ms 332 KB correct
26 Correct 2 ms 332 KB correct
27 Correct 2 ms 332 KB correct
28 Correct 1 ms 332 KB correct
29 Correct 1 ms 332 KB correct
30 Correct 2 ms 332 KB correct
31 Correct 2 ms 332 KB correct
32 Correct 2 ms 332 KB correct
33 Correct 2 ms 332 KB correct
34 Incorrect 197 ms 1620 KB WA in grader: NO
35 Halted 0 ms 0 KB -