oj.uz

Submission #757864

# Submission time Handle Problem Language Result Execution time Memory
757864 2023-06-13T20:41:25 Z alexander707070 Simurgh (IOI17_simurgh) C++14
30 / 100
 156 ms 4100 KB 
#include<bits/stdc++.h>
#include "simurgh.h"
#define MAXN 507
#define MAXM 300007
using namespace std;
 
int n,m,a[MAXM],b[MAXM],res[MAXM],t,good;
vector< pair<int,int> > vv[MAXN];
bool li[MAXN];
vector<int> tree,ask,g[MAXN],ans;
int curr,where[MAXN],maxres;
bool golden[MAXM],checked[MAXM],first;
int dsu[MAXN];

int root(int x){
	if(dsu[x]==x)return x;
	dsu[x]=root(dsu[x]);
	return dsu[x];
}
 
void dfs(int x){
	li[x]=true;
	for(int i=0;i<vv[x].size();i++){
		if(li[vv[x][i].first])continue;
 
		tree.push_back(vv[x][i].second);
		dfs(vv[x][i].first);
	}
}
 
void comp(int x,int p,int id){
	where[x]=id;
	for(int i=0;i<g[x].size();i++){
		if(g[x][i]==p)continue;
		comp(g[x][i],x,id);
	}
}
 
vector<int> find_roads(int N,vector<int> from,vector<int> to){
	n=N; m=int(from.size());

	for(int i=0;i<n;i++){
		dsu[i]=i;
	}
 
	for(int i=0;i<m;i++){
		a[i]=from[i]; b[i]=to[i];
 
		vv[a[i]].push_back({b[i],i});
		vv[b[i]].push_back({a[i],i});
	}

	for(int i=0;i<n;i++){
		random_shuffle(vv[i].begin(),vv[i].end());
	}
 
	dfs(0);
	random_shuffle(tree.begin(),tree.end());
	
	for(int i=0;i<n-1;i++){
		for(int f=0;f<n;f++)g[f].clear();
		ask.clear();
 
		for(int f=0;f<n-1;f++){
			if(i==f)continue;
 
			ask.push_back(tree[f]);
			g[a[tree[f]]].push_back(b[tree[f]]);
			g[b[tree[f]]].push_back(a[tree[f]]);
		}
 
		comp(a[tree[i]],-1,1);
		comp(b[tree[i]],-1,2);

 
		maxres=0; first=true; good=-1;
		for(int f=0;f<m;f++){
			res[f]=0;
			if(where[a[f]]!=where[b[f]] and (root(a[f])!=root(b[f]) or (first and golden[f]))){
				if(root(a[f])==root(b[f]))first=false;

				ask.push_back(f);
				res[f]=count_common_roads(ask);

				if(res[f]>maxres and maxres>0)good=res[f];

				if(res[f]==good){
					golden[f]=true;
					dsu[root(a[f])]=root(b[f]);
				}

				maxres=max(maxres,res[f]);
				ask.pop_back();
			}
		}
 
		for(int f=0;f<m;f++){
			if(where[a[f]]!=where[b[f]] and res[f]==maxres){
				golden[f]=true;
				dsu[root(a[f])]=root(b[f]);
			}
		}
	}
 
	for(int i=0;i<m;i++){
		if(golden[i]){
			ans.push_back(i);
		}
	}
 
	return ans;
}

Compilation message

simurgh.cpp: In function 'void dfs(int)':
simurgh.cpp:23:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for(int i=0;i<vv[x].size();i++){
      |              ~^~~~~~~~~~~~~
simurgh.cpp: In function 'void comp(int, int, int)':
simurgh.cpp:33:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i=0;i<g[x].size();i++){
      |              ~^~~~~~~~~~~~

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB correct
2 Correct 0 ms 340 KB correct
3 Correct 0 ms 340 KB correct
4 Correct 0 ms 340 KB correct
5 Correct 0 ms 340 KB correct
6 Correct 0 ms 340 KB correct
7 Correct 1 ms 340 KB correct
8 Correct 0 ms 340 KB correct
9 Correct 1 ms 340 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 1 ms 340 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 1 ms 340 KB correct
14 Correct 6 ms 428 KB correct
15 Correct 4 ms 340 KB correct
16 Correct 5 ms 436 KB correct
17 Correct 5 ms 340 KB correct
18 Correct 3 ms 340 KB correct
19 Correct 8 ms 340 KB correct
20 Correct 4 ms 428 KB correct
21 Correct 6 ms 416 KB correct
22 Correct 4 ms 340 KB correct
23 Correct 3 ms 340 KB correct
24 Correct 3 ms 340 KB correct
25 Correct 1 ms 340 KB correct
26 Correct 4 ms 344 KB correct
27 Correct 2 ms 340 KB correct
28 Correct 1 ms 340 KB correct
29 Correct 1 ms 340 KB correct
30 Correct 5 ms 340 KB correct
31 Correct 3 ms 340 KB correct
32 Correct 5 ms 396 KB correct
33 Correct 5 ms 340 KB correct
34 Incorrect 156 ms 1664 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 340 KB correct
2 Correct 1 ms 340 KB correct
3 Incorrect 122 ms 4100 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 340 KB correct
2 Correct 0 ms 340 KB correct
3 Correct 0 ms 340 KB correct
4 Correct 0 ms 340 KB correct
5 Correct 0 ms 340 KB correct
6 Correct 0 ms 340 KB correct
7 Correct 1 ms 340 KB correct
8 Correct 0 ms 340 KB correct
9 Correct 1 ms 340 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 1 ms 340 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 1 ms 340 KB correct
14 Correct 6 ms 428 KB correct
15 Correct 4 ms 340 KB correct
16 Correct 5 ms 436 KB correct
17 Correct 5 ms 340 KB correct
18 Correct 3 ms 340 KB correct
19 Correct 8 ms 340 KB correct
20 Correct 4 ms 428 KB correct
21 Correct 6 ms 416 KB correct
22 Correct 4 ms 340 KB correct
23 Correct 3 ms 340 KB correct
24 Correct 3 ms 340 KB correct
25 Correct 1 ms 340 KB correct
26 Correct 4 ms 344 KB correct
27 Correct 2 ms 340 KB correct
28 Correct 1 ms 340 KB correct
29 Correct 1 ms 340 KB correct
30 Correct 5 ms 340 KB correct
31 Correct 3 ms 340 KB correct
32 Correct 5 ms 396 KB correct
33 Correct 5 ms 340 KB correct
34 Incorrect 156 ms 1664 KB WA in grader: NO
35 Halted 0 ms 0 KB -