Submission #982854

#	Time	Username	Problem	Language	Result	Execution time	Memory
982854		Lalic	Simurgh (IOI17_simurgh)	C++17	0 / 100	0 ms	456 KiB

simurgh

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

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5+10;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int pai[505], peso[505], mark[505];

vector<pii> adj[505];

int find(int x){ return (pai[x]==x ? x : pai[x]=find(pai[x])); }
void join(int a, int b){
	a=find(a); b=find(b);
	if(a==b) return;
	
	if(peso[a]>peso[b]) swap(a, b);
	pai[a]=b;
	peso[b]=max(peso[b], peso[a]+1);
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	int m=(int)u.size();
	
	vector<pii> aresta;
	
	for(int i=0;i<m;i++){
		aresta.pb({u[i], v[i]});
		adj[u[i]].pb({v[i], i});
		adj[v[i]].pb({u[i], i});
	}
	
	vector<int> sk(m);
	vector<pii> royal;
	for(int i=0;i<n;i++){
		if(mark[i]) continue;
		
		for(int j=0;j<n;j++) pai[j]=j;
		
		vector<int> curr;
		for(auto at : royal) join(at.fi, at.se);
		for(int j=0;j<m;j++){
			pii at=aresta[j];
			
			if(sk[j]){
				curr.pb(at.se);
				continue;
			}
			if(at.fi==i || at.se==i) continue;
			
			if(find(at.fi)!=find(at.se)){
				join(at.fi, at.se);
				curr.pb(j);
			}
		}
		
		vector<int> lh={adj[i][0].se}, rh;
		curr.pb(adj[i][0].se);
		
		int ini=count_common_roads(curr);
		curr.pop_back();
		
		bool useRH=0;
		
		for(int j=1;j<(int)adj[i].size();j++){
			curr.pb(adj[i][j].se);
			
			int qnt=count_common_roads(curr);
			
			curr.pop_back();
			
			if(qnt!=ini){
				if(qnt>ini) useRH=1;
				rh.pb(adj[i][j].se);
			}
			else lh.pb(adj[i][j].se);
		}
		
		if(!useRH){
			for(auto at : lh){
				royal.pb(aresta[at]);
				sk[at]=1;
				mark[aresta[at].fi]=1;
				mark[aresta[at].se]=1;
			}
		}
		else{
			for(auto at : rh){
				royal.pb(aresta[at]);
				sk[at]=1;
				mark[aresta[at].fi]=1;
				mark[aresta[at].se]=1;
			}
		}
	}
	
	vector<int> ans;
	for(int i=0;i<m;i++)
		if(sk[i]) ans.pb(i);
		
	return ans;
}

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