Submission #582899

#	Time	Username	Problem	Language	Result	Execution time	Memory
582899		Koosha_mv	Simurgh (IOI17_simurgh)	C++14	100 / 100	243 ms	14144 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
 
const int N=505*505;
 
int n,m,askt,h[N],ok[N],vis[N],last[N],f[N],A[N],B[N],mark[N];
pair<int,int> par[N];
vector<int> tree;
vector<pair<int,int>> g[N];

int getpar(int u){
	if(f[u]<0) return u;
	return f[u]=getpar(f[u]);
}
void merge(int u,int v){
	u=getpar(u),v=getpar(v);
	if(f[u]>f[v]) swap(u,v);
	f[u]+=f[v];
	f[v]=u;
}
int ask(vector<int> vec){
	return count_common_roads(vec);
}
int get(vector<int> vec){
	fill(f,f+n,-1);
	int sum=0;
	for(auto id : vec){
		merge(A[id],B[id]);
	}
	for(auto id : tree){
		int u=getpar(A[id]),v=getpar(B[id]);
		if(u==v) continue ;
		merge(u,v);
		vec.pb(id);
		sum+=ok[id];
	}
	return ask(vec)-sum;
}
void dfs(int u){
	vis[u]=1;
	for(auto [v,id] : g[u]){
		if(vis[v]) continue ;
		tree.pb(id);
		h[v]=h[u]+1;
		par[v]={u,id};
		dfs(v);
	}
}
vector<int> G(vector<int> vec,int ad,int dl){
	vec.pb(ad);
	f(i,0,vec.size()){
		if(vec[i]==dl){
			vec.erase(vec.begin()+i);
		}
	}
	return vec;
}
vector<int> P(int u,int x){
	vector<int> res;
	f(i,0,x+1){
		res.pb(g[u][i].S);
	}
	return res;
}
vector<int> find_roads(int _n,vector<int> _B,vector<int> _A){
	fill(ok,ok+N,-1);
	// build graph
	vector<int> ans;
	n=_n,m=_A.size();
	f(i,0,m) A[i]=_A[i],B[i]=_B[i],g[A[i]].pb({B[i],i}),g[B[i]].pb({A[i],i});
	
	//find a tree
	dfs(0);
	askt=ask(tree);
	f(i,0,m){
		int u=A[i],v=B[i],mx=askt,cnt=0,edge=0;
		if(abs(h[u]-h[v])==1) continue ;
		if(h[u]>h[v]) swap(u,v);
		for(int x=v;x!=u;x=par[x].F){
			if(ok[par[x].S]!=-1){
				cnt++;
				edge=par[x].S;
			}
		}
		if(cnt==h[v]-h[u]) continue ;
		//cout<<u<<" -> "<<v<<endl;
		if(cnt>0){
			vector<int> prt=G(tree,i,edge);
			maxm(mx,ask(prt)+ok[edge]);
		}
		for(int x=v;x!=u;x=par[x].F){
			if(ok[par[x].S]!=-1) continue ;
			vector<int> prt=G(tree,i,par[x].S);
			last[par[x].S]=ask(prt);
			maxm(mx,last[par[x].S]);
		}
		for(int x=v;x!=u;x=par[x].F){
			if(ok[par[x].S]!=-1) continue ;
			if(last[par[x].S]==mx) ok[par[x].S]=0;
			else ok[par[x].S]=1;
		}
	}
	for(auto id : tree) if(ok[id]==-1) ok[id]=1;
	//dbga(ok,0,m);
	
	//main
	f(u,0,n){
		f_(i,g[u].size()-1,0) if(mark[g[u][i].S]) g[u].erase(g[u].begin()+i);
		vector<int> vec;
		int deg=get(P(u,g[u].size()-1));
		f(i,0,deg){
			int l=-1,r=g[u].size();
			while(l+1<r){
				int mid=(l+r)>>1;
				if(get(P(u,mid))<=i){
					l=mid;
				}
				else{
					r=mid;
				}
			}
			mark[g[u][r].S]=1;
			ans.pb(g[u][r].S);
		}
	}
	sort(all(ans));
	ans.resize(unique(all(ans))-ans.begin());
	return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'void dfs(int)':
simurgh.cpp:61:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |  for(auto [v,id] : g[u]){
      |           ^
simurgh.cpp: In function 'std::vector<int> G(std::vector<int>, int, int)':
simurgh.cpp:9:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   71 |  f(i,0,vec.size()){
      |    ~~~~~~~~~~~~~~              
simurgh.cpp:71:2: note: in expansion of macro 'f'
   71 |  f(i,0,vec.size()){
      |  ^

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