Submission #1326655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326655		thelegendary08	Simurgh (IOI17_simurgh)	C++17	0 / 100	1 ms	332 KiB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define vi vector<int>
#define f0r(i,n) for(int i = 0; i < n; i++)
#define dout(x) cout<<x<<' '<<#x<<endl;
#define dout2(x,y) cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl;
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<endl;
using namespace std; 
const int mxn = 505; 
vector<pair<int,int>>adj[mxn];
bool vis[mxn]; pair<int,int>from[mxn]; bool ok; int cur, head; vi egs, nodes, status; 
mt19937 rng(1911); 
void dfs(int node, int fr){
	if(ok)return;
	for(auto [u,id] : adj[node]){
		if(ok)return;
		// if(status[id]==0)continue;
		if(!vis[u]){
			vis[u] = 1, from[u] = mp(node, id); dfs(u, node); 
		}
		else if(u != fr){
			cur = node, head = u; egs.pb(id); ok = 1; return;
		}
	}
}
double dtime = 0, btime = 0; 
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	vector<int>zero = {0}; if(n==2)return zero; 
	f0r(i,n)adj[i].clear(); int m = u.size(); f0r(i,m)if(u[i]>v[i])swap(u[i],v[i]);
	f0r(i,m)adj[u[i]].pb(mp(v[i],i)),adj[v[i]].pb(mp(u[i],i));
	vi g(n); f0r(i,m){if(u[i]+1==v[i])g[u[i]]=i; if(u[i]==0&&v[i]==n-1)g[n-1]=i;}
	vi f(n); int mx = -1; vi mxd; f0r(i,n){
		vi quer; f0r(j,n)if(i!=j)quer.pb(g[j]); int ret = count_common_roads(quer);
		if(ret > mx)mx=ret,mxd={i}; else if(ret==mx)mxd.pb(i);
	}//mx = removed bad edge 
	// vout(mxd); cout<<"MXD\n";
	vi ans; f0r(i,n)f[i]=1; for(auto u : mxd)f[u]=0; f0r(i,n)if(f[i])ans.pb(g[i]); 
	// for(auto u : f)cout<<u<<' '; cout<<"F\n";
	vector<vector<int>> w(n, vi(n)); f0r(i,m)w[u[i]][v[i]]=i,w[v[i]][u[i]]=i;
	f0r(i,n){
		//(i,i+2),(i,i+3),...,(i,n-1)
		int pv = i + 2; 
		while(1){
			int lo = pv, hi = n; while(lo < hi){
				int mid = lo + (hi-lo) / 2; //mid~n-1 connect to i, before that create chain
				vi quer; int minus = 0; f0r(j,mid-1)quer.pb(g[j]),minus+=f[j]; for(int j = mid; j < n; j++)quer.pb(w[i][j]);
				int ret = count_common_roads(quer); ret -= minus; if(ret > 0)hi=mid; else lo=mid+1;
			} if(lo>=n)break; ans.pb(w[i][lo]); pv = lo + 1; 
		}
	}
	set<int>gg; for(auto u : ans)gg.insert(u); vi anss; for(auto u : gg)anss.pb(u); return anss; 
	/*
	status.resize(m); f0r(i,m)status[i]=-1; queue<int>q; 
	while(1){
		f0r(i,n)from[i] = mp(-1,-1); cur = -1; ok = 0; egs.clear(); nodes.clear(); int rt = rng() % n; 
		f0r(i,n)vis[i]=0; vis[rt] = 1;
		int t1 = std::chrono::system_clock::now().time_since_epoch().count(); dfs(rt,-1); int t2 = std::chrono::system_clock::now().time_since_epoch().count();
		dtime += t2 - t1; //for(auto u : from)cout<<u.F<<' '<<u.S<<'\n'; 
		if(cur==-1)break; while(1){
			nodes.pb(cur); if(from[cur].S != -1)egs.pb(from[cur].S); cur = from[cur].F; nodes.pb(cur); if(cur==head)break;
		}
		int mn = -1; set<int>rem; //vout(nodes); 
		// cout<<"egs "; for(auto u : egs)cout<<u<<' '; cout<<'\n';
		vi qq; vector<bool>vis(n); for(auto u : nodes)q.push(u), vis[u] = 1;
		t1 = std::chrono::system_clock::now().time_since_epoch().count();
		while(!q.empty()){
			int node = q.front(); q.pop(); for(auto [u,id] : adj[node]){
				if(!vis[u])vis[u]=1, qq.pb(id), q.push(u);
			}
		}
		t2 = std::chrono::system_clock::now().time_since_epoch().count(); btime += t2 - t1; 
		for(auto eg : egs){
			if(status[eg] != -1)continue;
			vi quer=qq; for(auto ed : egs)if(ed != eg)quer.pb(ed); 
			int ret = count_common_roads(quer); if(ret > mn)mn = ret, rem.clear(), rem.insert(eg); else if(ret == mn)rem.insert(eg); 
		}
		for(auto eg : egs){
			if(rem.count(eg)){
				adj[u[eg]].erase(find(adj[u[eg]].begin(),adj[u[eg]].end(),mp(v[eg], eg))); adj[v[eg]].erase(find(adj[v[eg]].begin(),adj[v[eg]].end(),mp(u[eg],eg))); 
				status[eg] = 0; 
			}
			else status[eg] = 1; 
		} //vout(status); 
		// int sum = 0; f0r(i,n)sum+=adj[i].size(); sum/=2; dout(sum);
	} f0r(i,m)if(status[i]==-1)status[i]=1;
	vi ans; f0r(i,m)if(status[i] == 1)ans.pb(i); //dout2(dtime/1e9, btime/1e9);
	return ans; 
	*/
	/*
	std::vector<int> r(n - 1);
	for(int i = 0; i < n - 1; i++)
		r[i] = i;
	int common = count_common_roads(r);
	if(common == n - 1)
		return r;
	r[0] = n - 1;
	return r;
	*/
}
/*
4
6
0 1
0 2
0 3
1 2
1 3
2 3
0 1 2
*/

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