Submission #1058428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058428		shenfe1	Simurgh (IOI17_simurgh)	C++17	70 / 100	273 ms	14556 KiB

simurgh

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

#pragma GCC optimize("Ofast")

using namespace std;

#define pb push_back
#define pii pair<int,int>
#define sz(s) (int)s.size()
#define F first
#define S second
#define all(v) v.begin(),v.end()

const int MAX=2e5+10;

struct dsu{
	int f[MAX];

	void init(int n){
		for(int i=0;i<n;i++)f[i]=i;
	}

	int get(int v){
		return (f[v]==v?v:f[v]=get(f[v]));
	}

	void unite(int a,int b){
		a=get(a),b=get(b);
		f[a]=b;
	}
}d;

int n;
vector<pii> g[MAX];
vector<int> u,v;
int is1[MAX],is0[MAX],dn[MAX];
int pr[MAX],dep[MAX];
set<int> st;

void dfs(int st){
	queue<int> q;
	q.push(st);
	while(!q.empty()){
		int v=q.front();
		q.pop();
		for(auto to:g[v]){
			if(pr[v]==to.S)continue;
			dep[to.F]=dep[v]+1;
			pr[to.F]=to.S;
			q.push(to.F);
		}
	}
}

int cq=1;

vector<int> vc(set<int> &st){
	vector<int> res;
	for(int i:st)res.pb(i);
	return res;
}

int add(vector<int> &vec){
	int CNT=0;
	d.init(n);
	vector<int> x;
	for(int i:vec){
		x.pb(i);
		d.unite(u[i],v[i]);
	}
	for(int i:st){
		if(d.get(u[i])!=d.get(v[i])){
			CNT+=is1[i];
			d.unite(u[i],v[i]);
			x.pb(i);
		}
	}
	cq++;
	// assert(cq<=8000);
	return count_common_roads(x)-CNT;
}

vector<int> find_roads(int N,vector<int> U,vector<int> V){
	n=N;
	u=U;
	v=V;
	vector<int> e;
	d.init(n);
	for(int i=0;i<sz(U);i++){
		if(d.get(U[i])!=d.get(V[i])){
			d.unite(U[i],V[i]);
			g[U[i]].pb({V[i],i});
			g[V[i]].pb({U[i],i});
			st.insert(i);
		}
		else e.pb(i);
	}
	for(int i=0;i<sz(U);i++)dn[i]=1;
	for(int i=0;i<n;i++)pr[i]=-1;
	dfs(0);
	int cnt=count_common_roads(vc(st));
	for(int num:e){
		int a=U[num],b=V[num];
		vector<int> canzam;
		int allv=0;
		int CNT=0;
		while(a!=b){
			CNT++;
			if(CNT>N){
				return vector<int>(n,-1);
			}
			if(dep[a]>dep[b]){
				canzam.pb(pr[a]);
				if(U[pr[a]]==a)a=V[pr[a]];
				else a=U[pr[a]];
			}
			else{
				canzam.pb(pr[b]);
				if(U[pr[b]]==b)b=V[pr[b]];
				else b=U[pr[b]];
			}
		}
		int ok=0;
		int canEdge=-1;
		for(int edge:canzam){
			if(dn[edge])allv=1;
			if(is1[edge]){
				ok=1;
				canEdge=edge;
			}
			else if(is0[edge]){
				ok=2;
				canEdge=edge;
			}
		}
		if(!allv)continue;
		if(ok==0){
			for(int edge:canzam){
				assert(dn[edge]);
				st.erase(edge);
				st.insert(num);
				cq++;
				int ncnt=count_common_roads(vc(st));
				if(ncnt<cnt){
					dn[edge]=0;
					is1[edge]=1;
					dn[num]=0;
					is0[num]=1;
				}
				else if(ncnt>cnt){
					dn[edge]=0;
					is0[edge]=1;
					dn[num]=0;
					is1[num]=1;
				}
				st.insert(edge);
				st.erase(num);
			}
			if(dn[num]){
				dn[num]=0;
				is0[num]=1;
				for(int edge:canzam){
					dn[edge]=0;
					is0[edge]=1;
				}
			}
			else{
				for(int edge:canzam){
					if(dn[edge]){
						dn[edge]=0;
						is0[edge]=is0[num];
						is1[edge]=is1[num];
					}
				}
			}
		}
		else if(ok==1){
			st.erase(canEdge);
			st.insert(num);
			int ncnt=count_common_roads(vc(st));
			cq++;
			st.insert(canEdge);
			st.erase(num);
			dn[num]=0;
			if(ncnt==cnt){
				is1[num]=1;
			}
			else{
				is0[num]=1;
			}
		}
		else{
			st.erase(canEdge);
			st.insert(num);	
			int ncnt=count_common_roads(vc(st));
			cq++;
			st.insert(canEdge);
			st.erase(num);
			dn[num]=0;
			if(ncnt==cnt){
				is0[num]=1;
			}
			else{
				is1[num]=1;
			}
		}
		for(int edge:canzam){
			if(dn[edge]){
				dn[edge]=0;
				st.insert(num);
				st.erase(edge);
				cq++;
				int ncnt=count_common_roads(vc(st));
                st.erase(num);
				st.insert(edge);
				if(ncnt==cnt){
					is0[edge]=is0[num];
					is1[edge]=is1[num];
				}
				else{
					is0[edge]=1-is0[num];
					is1[edge]=1-is1[num];
				}
			}
		}
	}
	assert(cq<=2*n+1);
	for(int edge:st){
		if(dn[edge]){
			dn[edge]=0;
			is1[edge]=1;
		}
	}
	for(int i=0;i<n;i++){
		g[i].clear();
	}
	for(int i=0;i<sz(u);i++){
		g[u[i]].pb({v[i],i});
		g[v[i]].pb({u[i],i});
	}
	for(int i=0;i<n;i++){
		vector<int> vec;
		for(auto to:g[i]){
			if(!st.count(to.S))vec.pb(to.S);
		}
		int cnt=add(vec);
		for(int j=1;j<=cnt;j++){
			int l=0,r=sz(g[i])-1,res=sz(g[i])-1;
			while(l<=r){
				int mid=(l+r)/2;
				vector<int> vec;
				for(int j=0;j<=mid;j++){
					if(!st.count(g[i][j].S))vec.pb(g[i][j].S);
				}
				if(add(vec)>=j){
					r=mid-1;
					res=mid;
				}
				else l=mid+1;
			}
			is1[g[i][res].S]=1;
		}
	}
	vector<int> ans;
	for(int i=0;i<sz(u);i++)if(is1[i])ans.pb(i);
	return ans;
}

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