oj.uz

Submission #612305

# Submission time Handle Problem Language Result Execution time Memory
612305 2022-07-29T12:51:41 Z chirathnirodha Simurgh (IOI17_simurgh) C++17
0 / 100
 131 ms 5292 KB 
#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define P push 
#define I insert 
#define F first 
#define S second

int n,m;
int ev[500][500];
vector<pair<int,int> > ed[500]; 
vector<int> g;
vector<int> chil[500];
int link[200000];
int royal[200000];
int parent[500];
int inival;
int flink(int x){
	if(x==link[x])return x;
	else return link[x];
}
vector<int> dfs(int x){
	bool insub[n];
	memset(insub,false,sizeof(insub));
	for(int i=0;i<chil[x].size();i++){
		int y=ed[x][i].F;
		vector<int> tm=dfs(y);
		for(int j=0;j<tm.size();j++)insub[tm[j]]=true;
	}
	if(x==0)return g;//Just to end the fundtion

	vector<int> nv;
	for(int i=0;i<n-1;i++)if(g[i]!=ev[x][parent[x]])nv.PB(g[i]);

	for(int i=0;i<ed[x].size();i++){
		int y=ed[x][i].F,z=ed[x][i].S;
		if(insub[y] || y==parent[x])continue;
		nv.PB(z);
		int d=count_common_roads(nv);
		nv.pop_back();

		int xtopar=ev[x][parent[x]];xtopar=flink(xtopar);
		int xtoy=ev[x][y];xtoy=flink(xtoy);
		
		if(d==inival){
			link[xtoy]=xtopar;
			if(royal[xtopar]==-1)royal[xtopar]=royal[xtoy];
		}
		else if(d>inival){
			royal[xtoy]=1;
			royal[xtopar]=0;
		}
		else{
			royal[xtopar]=1;
			royal[xtoy]=0;
		}
	}
	for(int i=0;i<ed[parent[x]].size();i++){
		if(parent[x]==0)continue;
		int y=ed[parent[x]][i].F,z=ed[parent[x]][i].S;
		if(insub[y]==false || y==x)continue;
		nv.PB(z);
		int d=count_common_roads(nv);
		nv.pop_back();

		int xtopar=ev[x][parent[x]];xtopar=flink(xtopar);
		int xtoy=ev[parent[x]][y];xtoy=flink(xtoy);
		
		if(d==inival){
			link[xtoy]=xtopar;
			if(royal[xtopar]==-1)royal[xtopar]=royal[xtoy];
		}
		else if(d>inival){
			royal[xtoy]=1;
			royal[xtopar]=0;
		}
		else{
			royal[xtopar]=1;
			royal[xtoy]=0;
		}
	}
	insub[x]=true;
	vector<int> subn;
	for(int i=0;i<n;i++)if(insub[i])subn.PB(i);
	return subn;
}
vector<int> find_roads(int N, vector<int> u, vector<int> v) {
	n=N;m=u.size();
	for(int i=0;i<m;i++){
		ev[u[i]][v[i]]=ev[v[i]][u[i]]=i;
		ed[u[i]].PB(MP(v[i],i));
		ed[v[i]].PB(MP(u[i],i));
	}
	memset(parent,-1,sizeof(parent));
	queue<int> q;q.P(0);parent[0]=0;
	while(!q.empty()){
		int c=q.front();q.pop();
		for(int i=0;i<ed[c].size();i++){
			int y=ed[c][i].F;
			if(parent[y]!=-1)continue;
			chil[c].PB(y);
			parent[y]=c;
			g.PB(ed[c][i].S);
			q.P(y);
		}
	}
	for(int i=0;i<m;i++)link[i]=i;
	memset(royal,-1,sizeof(royal));
	inival=count_common_roads(g);
	if(inival==n-1){
		for(int i=0;i<n-1;i++)royal[g[i]]=1;
	}
	dfs(0);
	vector<int> ans;
	for(int i=0;i<m;i++){
		royal[i]=royal[flink(i)];
		if(royal[i]==1)ans.PB(i);
	}
	return ans;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> dfs(int)':
simurgh.cpp:27:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i=0;i<chil[x].size();i++){
      |              ~^~~~~~~~~~~~~~~
simurgh.cpp:30:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for(int j=0;j<tm.size();j++)insub[tm[j]]=true;
      |               ~^~~~~~~~~~
simurgh.cpp:37: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]
   37 |  for(int i=0;i<ed[x].size();i++){
      |              ~^~~~~~~~~~~~~
simurgh.cpp:60: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]
   60 |  for(int i=0;i<ed[parent[x]].size();i++){
      |              ~^~~~~~~~~~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:100:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |   for(int i=0;i<ed[c].size();i++){
      |               ~^~~~~~~~~~~~~

Subtask #1
0 / 13.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB correct
2 Correct 1 ms 1108 KB correct
3 Incorrect 131 ms 5292 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 1108 KB correct
2 Correct 1 ms 1108 KB correct
3 Correct 1 ms 1108 KB correct
4 Incorrect 1 ms 1108 KB WA in grader: NO
5 Halted 0 ms 0 KB -