Submission #1082827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082827		amirhoseinfar1385	Simurgh (IOI17_simurgh)	C++17	13 / 100	11 ms	2648 KiB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+10;
vector<int>adj[maxn];
int n,m,vis[maxn],high[maxn],p[maxn];
pair<int,int>alle[maxn];
vector<int>dfsor;
map<pair<int,int>,int>lnk;
map<int,int>mp;
vector<int>res;
vector<int>adjt,updy;
struct dsu{
	int par[maxn];
	dsu(){
		for(int i=0;i<maxn;i++){
			par[i]=i;
		}
	}
	int root(int u){
		if(u==par[u]){
			return u;
		}
		return par[u]=root(par[u]);
	}
	int con(int u,int v){
		u=root(u);v=root(v);
		if(u==v){
			return 0;
		}
		par[u]=v;
		return 1;
	}
	void clear(){
		for(int i=0;i<maxn;i++){
			par[i]=i;
		}
	}
}ds;

int pors(set<int>st){
	vector<int>ers;
	for(auto x:st){
		ers.push_back(x);
	}
	return count_common_roads(ers);
}


bool check(vector<int>ch){
	ds.clear();
	int ent=0;
	set<int>ers;
	for(auto x:ch){
		ers.insert(x);
		ds.con(alle[x].first,alle[x].second);
	}
	for(auto x:adjt){
		if(ds.con(alle[x].first,alle[x].second)){
			ent+=mp[x];
			ers.insert(x);
		}
	}
	if(ent==pors(ers)){
		return 0;
	}
	return 1;
}

void upd(int ind){
	set<int>st;
	for(auto x:adjt){
		st.insert(x);
	}
	st.insert(ind);
	vector<int>alli;
	alli.push_back(ind);
	int mx=-1;
	int u=alle[ind].first,v=alle[ind].second;
	if(high[u]>high[v]){
		swap(u,v);
	}
	int cnt=-1;
	while(v!=u){
		alli.push_back(lnk[make_pair(v,p[v])]);
		v=p[v];
	}
	for(auto x:alli){
		if(mp.count(x)==1){
			cnt=x;
		}
	}
	if(cnt>=0){
		st.erase(cnt);
		int wtf=pors(st);
		st.insert(cnt);
		for(auto x:alli){
			if(mp.count(x)==0){
				st.erase(x);
				int tof=pors(st);
				st.insert(x);
				if(tof==wtf){
					mp[x]=mp[cnt];
				}else{
					mp[x]=mp[cnt]^1;
				}
				if(mp[x]){
					res.push_back(x);
				}
			}
		}
		return ;
	}
	for(auto x:alli){
		st.erase(x);
		mx=max(mx,pors(st));
		st.insert(x);
	}
	for(auto x:alli){
		if(mp.count(x)==1){
			continue;
		}
		st.erase(x);
		if(mx==pors(st)){
			mp[x]=0;
		}else{
			mp[x]=1;
			res.push_back(x);
		}
		st.insert(x);
	}
}

pair<int,int>buildt(int u=0,int par=-1){
	vis[u]=1;
	p[u]=par;
	pair<int,int>ret=make_pair(high[u],m);
	for(auto x:adj[u]){
		if(vis[x]==0){
			high[x]=high[u]+1;
			ret=min(ret,buildt(x,u));
			adjt.push_back(lnk[make_pair(u,x)]);
		}
	}
	for(auto x:adj[u]){
		if(x!=par){
		   ret=min(ret,make_pair(high[x],lnk[make_pair(u,x)]));
		}
	}
	if(u!=0){
		if(mp.count(lnk[make_pair(u,par)])==1){
			return ret;
		}
		if(ret.first>=high[u]){
			mp[lnk[make_pair(u,par)]]=1;
			res.push_back(lnk[make_pair(u,par)]);
		}else{
			updy.push_back(ret.second);
		}
	}
	return ret;
}

void erasea(){
	sort(adjt.begin(),adjt.end());
	set<int>sth;
	for(auto x:adjt){
		if(mp.count(x)==0){
			exit(23);
		}
		sth.insert(x);
	}
	for(int i=0;i<n;i++){
		vector<int>fake;
		for(auto x:adj[i]){
			if(mp.count(lnk[make_pair(i,x)])==0&&i<x){
				fake.push_back(x);
			}
		}
		swap(adj[i],fake);
	}
}

void bagh(){
	for(int i=0;i<n;i++){
		int low=0;
		while(low<(int)adj[i].size()){
			int high=(int)adj[i].size(),mid;
			while(high-low>=1){
				mid=(high+low)>>1;
				vector<int>ch;
				for(int j=low;j<=mid;j++){
					ch.push_back(lnk[make_pair(i,adj[i][j])]);
				}
				if(check(ch)){
					high=mid;
				}else{
					low=mid+1;
				}
			}
			if(high!=adj[i].size()){
				res.push_back(lnk[make_pair(i,adj[i][high])]);
				low=high+1;
			}
		}
	}
}

vector<int>solve(){
	buildt();
	for(auto x:res){
		//cout<<"magemishe "<<x<<endl;
	}
	for(auto x:updy){
		upd(x);
	}
	for(auto x:adjt){
		//cout<<"ha: "<<x<<endl;
	}
	for(auto x:res){
		//cout<<"magemishe "<<x<<endl;
	}
	erasea();
	bagh();
	return res;
}

std::vector<int> find_roads(int n_, std::vector<int> u, std::vector<int> v){
	m=(int)u.size();
	n=n_;
	for(int i=0;i<m;i++){
		lnk[make_pair(u[i],v[i])]=lnk[make_pair(v[i],u[i])]=i;
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
		alle[i]=make_pair(u[i],v[i]);
	}
	return solve();
}

Compilation message (stderr)

simurgh.cpp: In function 'void bagh()':
simurgh.cpp:201:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |    if(high!=adj[i].size()){
      |       ~~~~^~~~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> solve()':
simurgh.cpp:211:11: warning: unused variable 'x' [-Wunused-variable]
  211 |  for(auto x:res){
      |           ^
simurgh.cpp:217:11: warning: unused variable 'x' [-Wunused-variable]
  217 |  for(auto x:adjt){
      |           ^
simurgh.cpp:220:11: warning: unused variable 'x' [-Wunused-variable]
  220 |  for(auto x:res){
      |           ^

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