Submission #790680

#	Time	Username	Problem	Language	Result	Execution time	Memory
790680		ttamx	Simurgh (IOI17_simurgh)	C++14	13 / 100	16 ms	3668 KiB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>

using namespace std;

const int N=505;
const int M=15005;

int n,m;
vector<int> adj[N];
vector<int> edge,ans;
int eu[M],ev[M];
bool vis[N],used[M];
int pa[N],pa2[M];
int val[M];

int fp(int u){
	if(pa[u]==u)return u;
	return pa[u]=fp(pa[u]);
}

int fp2(int u){
	if(pa2[u]==u)return u;
	return pa2[u]=fp2(pa2[u]);
}

int go(int u,int i){
	return u^eu[i]^ev[i];
}

bool valid(){
	iota(pa,pa+n,0);
	for(auto i:edge){
		int u=fp(eu[i]),v=fp(ev[i]);
		if(u==v)return false;
		pa[u]=v;
	}
	return true;
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	::n=n;
	m=u.size();
	for(int i=0;i<u.size();i++){
		eu[i]=u[i];
		ev[i]=v[i];
		adj[u[i]].emplace_back(i);
		adj[v[i]].emplace_back(i);
	}
	iota(pa2,pa2+m,0);
	queue<int> q;
	vis[0]=true;
	q.emplace(0);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(auto i:adj[u]){
			int v=go(u,i);
			if(vis[v])continue;
			vis[v]=true;
			q.emplace(v);
			edge.emplace_back(i);
		}
	}
	int res=count_common_roads(edge);
	if(res==n-1)return edge;
	for(auto i:edge)used[i]=true;
	for(int i=0;i<n-1;i++){
		int e=edge[i];
		for(int j=0;j<m;j++){
			if(used[j])continue;
			edge[i]=j;
			if(!valid()){
				edge[i]=e;
				continue;
			}
			int tmp=count_common_roads(edge);
			edge[i]=e;
			if(res==tmp){
				if(fp2(e)!=fp2(j)){
					pa2[fp2(e)]=fp2(j);
					val[fp2(e)]|=val[fp2(j)];
				}
			}else if(tmp>res){
				val[fp2(j)]|=1;
				val[fp2(e)]|=2;
			}else{
				val[fp2(j)]|=2;
				val[fp2(e)]|=1;
			}
		}
	}
	for(int i=0;i<m;i++)if(val[fp2(i)]!=2)ans.emplace_back(i);
	return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:44:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i=0;i<u.size();i++){
      |              ~^~~~~~~~~

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