Submission #831760

#	Time	Username	Problem	Language	Result	Execution time	Memory
831760		Antekb	Simurgh (IOI17_simurgh)	C++17	100 / 100	150 ms	5792 KiB

simurgh

#include<bits/stdc++.h>
#include "simurgh.h"
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pp pop_back
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<pii>;
using ll = long long;

void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);

const int N=505;
int r[N], vis[N], par[N], paredg[N], dep[N];
int dobry[N];
int deg[N];
vii E[N];
vii edg;
int n;
int find(int v){
	if(r[v]==v)return v;
	return r[v]=find(r[v]);
}
void Union(int u, int v){
	r[find(u)]=find(v);
}
void dfs(int v){
	vis[v]=1;
	for(auto ee:E[v]){
		int u=ee.st, e=ee.nd;
		//deb(v, u);
		if(!vis[u]){
			paredg[u]=e;
			par[u]=v;
			dep[u]=dep[v]+1;
			dfs(u);
		}
	}
}
vii drz;
int queries=0;
int licz(vi V){
	for(int i=0; i<n; i++){
		r[i]=i;
	}
	vi V2;
	int sum=0;
	for(int i:V){
		V2.pb(i);
		Union(edg[i].st, edg[i].nd);
	}
	for(pii i:drz){
		if(find(edg[i.st].st)!=find(edg[i.st].nd)){
			sum+=i.nd;
			V2.pb(i.st);
			Union(edg[i.st].st, edg[i.st].nd);
		}
	}
	assert(queries++<25000);
	int ile=count_common_roads(V2);
	return ile-sum;
}
std::vector<int> find_roads(int _n, std::vector<int> _u, std::vector<int> _v) {
	n=_n;
	for(int i=0; i<_u.size(); i++)
	{
		E[_u[i]].eb(_v[i], i);
		E[_v[i]].eb(_u[i], i);
		edg.eb(_u[i], _v[i]);
	}
	par[0]=paredg[0]=-1;
	dfs(0);
	vi V;
	for(int i=1; i<n; i++){
		r[i]=i;
		deb(i, par[i], paredg[i], dep[i]);
		V.pb(paredg[i]);
	}
	int ile=count_common_roads(V);
	for(int v=0; v<n; v++){
		for(pii ee:E[v]){
			int u=ee.st, e=ee.nd;
			if(dep[u]>dep[v] && v!=par[u]){
				vi todo;
				//deb(v, u);
				while(true){
					int uu=find(u);
					if(uu==find(v)){
						break;
					}
					else{
						int e2=paredg[uu];
						for(int &i:V){
							if(i==e2)i=e;
						}
	assert(queries++<25000);
						int ile2=count_common_roads(V);
						if(ile2==ile){
							//deb(e2);
							todo.pb(e2);
						}
						else if(ile2>ile){
							//kraw=e;
						}
						else{
							dobry[uu]=1;
							//kraw=e2;
						}
						r[uu]=par[uu];
						for(int &i:V){
							if(i==e)i=e2;
						}
					}
				}
				if(todo.empty())continue;
				for(int uu=u; uu!=v; uu=par[uu]){
					bool czy=0;
					for(int i:todo){
						if(i==paredg[uu]){
							czy=1;
							break;
						}
					}
					if(czy)continue;
					//deb("a");
					int e2=paredg[uu];
					for(int &i:V){
						if(i==e2)i=e;
					}
	assert(queries++<25000);
					int ile2=count_common_roads(V);
					if(ile2+dobry[u]>ile){
						//deb("b");
						for(int i:todo){
							if(i==paredg[edg[i].st])dobry[edg[i].st]=1;
							else dobry[edg[i].nd]=1;
						}
					}
					for(int &i:V){
						if(i==e)i=e2;
					}
					break;
				}
			}
		}
	}
	for(int i=1; i<n; i++){
		if(find(i)==i){
			dobry[i]=1;
		}
		deb(i, find(i), paredg[i], dobry[i]);
		drz.eb(paredg[i], dobry[i]);
	}
	for(int i=0; i<n; i++){
		vis[i]=0;
		vi V2;
		for(auto e:E[i]){
			V2.pb(e.nd);
		}
		deg[i]=licz(V2);
		deb(i, deg[i]);
	}
	vi ans;
	for(int ii=1; ii<n; ii++){
		int v=-1;
		for(int i=0; i<n; i++){
			if(!vis[i] && deg[i]==1){
				v=i;
			}
		}
		vi V2;
		assert(v!=-1);
		for(auto e:E[v]){
			if(!vis[e.st])V2.pb(e.nd);
		}
		int l=0, r=V2.size()-1;
		while(l<r){
			int m=(l+r)>>1;
			vi V3=V2;
			V3.resize(m+1);
			if(licz(V3)==0)l=m+1;
			else r=m;
		}
		ans.pb(V2[l]);
		int u=edg[ans.back()].st^edg[ans.back()].nd^v;
		deg[u]--;
		deg[v]--;
		vis[v]=1;
	}
	return ans;
}

Compilation message (stderr)

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

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