Submission #137672

#	Time	Username	Problem	Language	Result	Execution time	Memory
137672		ckodser	Simurgh (IOI17_simurgh)	C++14	70 / 100	201 ms	12484 KiB

simurgh

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

#define ll int
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll maxn=510;
const ll inf=1e9+900;

ll d[maxn];
vector<ll> s,t;
ll ger[maxn][maxn];
ll hast[maxn][maxn];
ll barg,N,M;

ll c_c_r(vector<ll> r){
    return count_common_roads(r);
}

bool backedge[maxn*maxn];
ll yal[maxn*maxn];
vector<ll> tree;
ll highback[maxn*maxn];
ll pare[maxn*maxn];

bool vis[maxn*maxn];
ll h[maxn];
vector<ll> child[maxn];
ll treeans;

pii dfs(ll a){
    vis[a]=1;
    pii best=mp(h[a],0);
    for(ll i=0;i<N;i++){
	if(ger[a][i]!=-1){
	    ll e=ger[a][i];
	    if(!vis[i]){
		child[a].pb(e);
		tree.pb(e);
		pare[i]=e;
		h[i]=h[a]+1;
		pii y=dfs(i);
		best=min(best,y);
		if(y.F<h[a]){
		    highback[e]=y.S;
		}else{
		    highback[e]=-1;
		}
	    }else if(h[i]>h[a]){
		backedge[e]=1;
		yal[e]=pare[i];
	    }else{
		best=min(best,mp(h[i],e));
	    }
	}
    }
    return best;
}
vector<pii> shart[maxn*maxn];
vector<ll> gruh[2];
void dfsShart(ll a,bool b){
    gruh[b].pb(a);
    vis[a]=1;
    for(auto e:shart[a]){
	if(!vis[e.F]){
	    dfsShart(e.F,e.S^b);
	}
    }
}



void findShart(ll a,ll b){
    vector<ll> r;
    for(auto e:tree){
	if(e==a)r.pb(b);
	else r.pb(e);
    }
    ll t=c_c_r(r);
    if(t==treeans){
	shart[a].pb(mp(b,0));
	shart[b].pb(mp(a,0));
    }else{
	shart[a].pb(mp(b,1));
	shart[b].pb(mp(a,1));
    }
}
ll pardsu[maxn];
ll findpardsu(ll a){
    if(pardsu[a]==a)return a;
    pardsu[a]=findpardsu(pardsu[a]);
    return pardsu[a];
}


vector<ll> getYal(vector<ll> g){
    for(ll i=0;i<maxn;i++){
	pardsu[i]=i;
    }
    vector<ll> r;
    for(auto yal:g){
	ll a=findpardsu(s[yal]);
	ll b=findpardsu(t[yal]);
	if(a==b){
	    return r;
	}else{
	    pardsu[a]=b;
	}
    }
    for(ll e=0;e<M;e++){
	ll a=findpardsu(s[e]);
	ll b=findpardsu(t[e]);
	if(a!=b){
	    pardsu[a]=b;
	    r.pb(e);
	}		
    }
    for(auto e:g)r.pb(e);
    return r;
}
vector<ll>  solve2(ll n){
    dfs(0);
    treeans=c_c_r(tree);
    for(ll e=0;e<M;e++){
	if(h[s[e]]>h[t[e]])swap(s[e],t[e]);
	if(backedge[e]){
	    findShart(yal[e],e);
	}
    }
    for(auto e:tree){
	if(highback[e]!=-1){
	    findShart(e,highback[e]);
	    findShart(pare[s[e]],highback[e]);
	}
    }
    memset(vis,0,sizeof vis);
    vector<ll> ans;
    for(auto e:tree){
	if(!vis[e]){
	    gruh[0].clear();
	    gruh[1].clear();
	    dfsShart(e,0);

	    vector<ll> r0=getYal(gruh[0]);
	    vector<ll> r1=getYal(gruh[1]);

	    if(r0.empty()){
		for(auto e:gruh[1])ans.pb(e);
	    }
	    else if(r1.empty()){
		for(auto e:gruh[0])ans.pb(e);
    	    }else{
		if(gruh[0].size()<gruh[1].size()){
			for(auto e:gruh[1])ans.pb(e);
		}
		if(gruh[0].size()>gruh[1].size()){
			for(auto e:gruh[0])ans.pb(e);
		}
		if(gruh[0].size()==gruh[1].size()){
		    ll d0=c_c_r(r0);
		    ll d1=c_c_r(r1);
		    if(d0>d1){
			for(auto e:gruh[0])ans.pb(e);
		    }else{
			for(auto e:gruh[1])ans.pb(e);

		    }
		}
	    }
	}
    }
    return ans;
}
ll findCnt(ll v,ll l,ll r){
    vector<ll> t;
    for(ll i=l;i<r;i++){
	if(i!=v && i!=barg){
	    t.pb(ger[v][i]);
	}
    }
    ll ans=0;
    ans-=hast[v][barg];
    t.pb(ger[v][barg]);
    for(ll i=0;i<l;i++){
	if(i!=v &&i!=barg){
	    t.pb(ger[barg][i]);
	    ans-=hast[barg][i];
	}
    }
    for(ll i=r;i<N;i++){
	if(i!=v && i!=barg){
	    t.pb(ger[barg][i]);
	    ans-=hast[barg][i];
	}
    }
    ans+=c_c_r(t);
    return ans;
}	
void findHam(ll v,ll l,ll r,ll x){
    if(l>=r)return;
    if(x==0)return;
    if(l+1==r){
	hast[v][l]=1;
	hast[l][v]=1;
	return;
    }
    ll mid=(l+r)/2;
    ll y=findCnt(v,l,mid);
    findHam(v,l,mid,y);
    findHam(v,mid,r,x-y);
}
void solve(ll n){
    barg=-1;
    for(ll i=0;i<n;i++){
	vector<ll> r;
	for(ll j=0;j<n;j++){
	    if(j!=i){
		r.pb(ger[i][j]);
	    }
	}
	d[i]=c_c_r(r);
	if(d[i]==1)barg=i;
    }
    for(ll i=0;i<n;i++){
	if(i!=barg){
	    vector<ll> r;
	    ll yeki=-1;
	    for(ll j=0;j<n;j++){
		if(j!=i && j!=barg){
		    yeki=j;
		    r.pb(ger[i][j]);
		}
	    }
	    r.pb(ger[barg][yeki]);

	    if(c_c_r(r)==d[i]-1){
		hast[barg][i]=1;
		hast[i][barg]=1;
		break;
	    }
	}
    }
    for(ll i=0;i<n;i++){
	if(i!=barg){
	    findHam(i,0,n,d[i]-hast[barg][i]);
	}
    }
}
vector<ll> findAnsE(ll n){
    vector<ll> ans;
    for(ll i=0;i<n;i++){
	for(ll j=i+1;j<n;j++){
	    if(hast[i][j]){
		ans.pb(ger[i][j]);
	    }
	}
    }
    sort(ans.begin(),ans.end());
    return ans;
}
vector<int> find_roads(int n,vector<int> u,vector<int> v) {
    N=n;
    if(n==2){
	vector<ll> ans;
	ans.pb(0);
	return ans;
    }
    memset(ger,-1,sizeof ger);
    s=v;
    t=u;
    ll m=v.size();
    M=m;
    for(ll i=0;i<m;i++){
	ger[s[i]][t[i]]=i;
	ger[t[i]][s[i]]=i;
    }
    if(m==(n*(n-1))/2){
	solve(n);
	return findAnsE(n);
    }
    if(n<=240){
	return solve2(n);
    }
    exit(1); 
}

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