Submission #612544

#	Time	Username	Problem	Language	Result	Execution time	Memory
612544		chirathnirodha	Simurgh (IOI17_simurgh)	C++17	13 / 100	157 ms	6520 KiB

simurgh

#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<pair<int,int> > alled;
int link[200000];
int royal[200000];
int find(int x){
	if(link[x]==x)return x;
	else return find(link[x]);
}
void func(int x){
	int parent[n];memset(parent,-1,sizeof(parent));
	vector<int> g;
	int uni[n];
	for(int h=0;h<n;h++){
		if(parent[h]!=-1 || h==x)continue;
		uni[h]=h;
		queue<int> q;q.P(h);
		parent[h]=h;
		while(!q.empty()){
			int c=q.front();q.pop();
			uni[c]=h;
			for(int i=0;i<ed[c].size();i++){
				int y=ed[c][i].F;
				if(parent[y]!=-1 || y==x)continue;
				parent[y]=c;
				g.PB(ed[c][i].S);
				q.P(y);
			}
		}
	}
	vector<pair<int,int> > v[n];
	for(int i=0;i<ed[x].size();i++){
		int y=ed[x][i].F,z=ed[x][i].S;
		v[uni[y]].PB(MP(royal[find(z)],z));
	}
	for(int i=0;i<n;i++){
		if(v[i].size()==0)continue;
		sort(v[i].begin(),v[i].end());
		g.PB(v[i].back().S);
	}

	int inival=count_common_roads(g);
	if(inival==n-1)for(int i=0;i<n-1;i++)royal[find(g[i])]=1;
	if(inival==0)for(int i=0;i<n-1;i++)royal[find(g[i])]=0;

	for(int i=0;i<n;i++){
		if(v[i].size()<=1)continue;

		vector<int> ng;
		int iniadd=v[i].back().S;
		for(int j=0;j<n-1;j++)if(g[j]!=iniadd)ng.PB(g[j]);

		for(int j=0;j<v[i].size()-1;j++){

			int ind=v[i][j].S;
			int lini=find(iniadd);int lcur=find(ind);
			if(royal[lcur]!=-1)break;
			int y=alled[ind].F;if(y==x)alled[ind].S;

			ng.PB(ind);
			int val=count_common_roads(ng);
			ng.pop_back();
			
			if(val==inival){
				link[lcur]=lini;
			}
			else if(val>inival){
				royal[lini]=0;
				royal[lcur]=1;
			}
			else {
				royal[lcur]=0;
				royal[lini]=1;
			}
		}
	}
	return;
} 
vector<int> find_roads(int N, vector<int> u, vector<int> v) {
	n=N;m=u.size();
	for(int i=0;i<m;i++){
		alled.PB(MP(u[i],v[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));
	}
	for(int i=0;i<m;i++)link[i]=i;
	memset(royal,-1,sizeof(royal));
	for(int i=0;i<n;i++)func(i);
	vector<int> ans;
	for(int i=0;i<m;i++)if(royal[find(i)]==1)ans.PB(i);
	return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'void func(int)':
simurgh.cpp:33:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |    for(int i=0;i<ed[c].size();i++){
      |                ~^~~~~~~~~~~~~
simurgh.cpp:43: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]
   43 |  for(int i=0;i<ed[x].size();i++){
      |              ~^~~~~~~~~~~~~
simurgh.cpp:64: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]
   64 |   for(int j=0;j<v[i].size()-1;j++){
      |               ~^~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30