Submission #302142

#	Time	Username	Problem	Language	Result	Execution time	Memory
302142		TMJN	Simurgh (IOI17_simurgh)	C++17	51 / 100	356 ms	1792 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

int N,M,T[500],tmpval[30000];
bool B[30000],checked[30000];
vector<int>res,tree;

static int par(int x){
	if(T[x]==x)return x;
	return T[x]=par(T[x]);
}

static bool uni(int x,int y){
	x=par(x);
	y=par(y);
	if(x==y)return false;
	T[x]=y;
	return true;
}

vector<int>find_roads(int n,vector<int>u,vector<int>v){
	N=n;
	M=u.size();
	res.clear();
	tree.clear();
	for(int i=0;i<N;i++){
		T[i]=i;
	}
	for(int i=0;i<M;i++){
		if(uni(u[i],v[i])){
			tree.push_back(i);
		}
		B[i]=checked[i]=false;
		tmpval[i]=0;
	}
	int tmp=count_common_roads(tree);
	for(int i:tree){
		tmpval[i]=tmp;
	}
	for(int i:tree){
		for(int j=0;j<N;j++){
			T[j]=j;
		}
		vector<int>K;
		for(int j:tree){
			if(i==j)continue;
			uni(u[j],v[j]);
			K.push_back(j);
		}
		K.push_back(-1);
		int t=-1;
		for(int j=0;j<M;j++){
			if(i==j)continue;
			if(par(u[j])!=par(v[j])){
				if(checked[j]){
					if(B[j]){
						t=j;
					}
				}
				else{
					K.back()=j;
					tmpval[j]=count_common_roads(K);
				}
			}
		}
		if(t==-1){
			int mx=0;
			for(int j=0;j<M;j++){
				if(par(u[j])!=par(v[j])&&!checked[j]){
					mx=max(mx,tmpval[j]);
				}
			}
			for(int j=0;j<M;j++){
				if(par(u[j])!=par(v[j])&&!checked[j]){
					if(tmpval[j]==mx){
						B[j]=true;
					}
					checked[j]=true;
				}
			}
		}
		else{
			K.back()=t;
			int hoge=count_common_roads(K);
			for(int j=0;j<M;j++){
				if(par(u[j])!=par(v[j])&&!checked[j]){
					if(tmpval[j]==hoge){
						B[j]=true;
					}
					checked[j]=true;
				}
			}
		}
	}
	for(int i=0;i<M;i++){
		if(B[i])res.push_back(i);
	}
	return res;
}

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