Submission #797531

#	Time	Username	Problem	Language	Result	Execution time	Memory
797531		alvingogo	Simurgh (IOI17_simurgh)	C++14	51 / 100	78 ms	5300 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct DSU{
	vector<int> bo;
	void init(int x){
		bo.resize(x);
		iota(bo.begin(),bo.end(),0);
	}
	int find(int x){
		return bo[x]==x?x:bo[x]=find(bo[x]);
	}
	int merge(int x,int y){
		x=find(x);
		y=find(y);
		if(x==y){
			return 0;
		}
		bo[x]=y;
		return 1;
	}
}dsu;

int query(const vector<int>& r){
	return count_common_roads(r);
}
vector<int> ans,vis;
vector<vector<pair<int,int> > > e;
struct TR{
	struct no{
		vector<pair<int,int> > ch;
		vector<int> sub;
	};
	vector<int> s;
	int pas;
	vector<no> v;
	int n;
	void init(int x){
		n=x;
		v.resize(n);
		for(int i=0;i<n;i++){
			v[i].sub.resize(n);
		}
	}
	void add(int x,int y,int t){
		v[x].ch.push_back({y,t});
		v[y].ch.push_back({x,t});
		s.push_back(t);
		vis[t]=1;
	}
	void dfs(int r,int f,int k){
		v[r].sub[r]=1;
		for(auto h:v[r].ch){
			if(h.fs!=f){
				dfs(h.fs,r,h.sc);
				for(int i=0;i<n;i++){
					v[r].sub[i]|=v[h.fs].sub[i];
				}
			}
		}
		if(r==f){
			return;
		}
		int val=-1;
		vector<int> ud;
		vector<int> l;
		for(int i=0;i<n;i++){
			if(v[r].sub[i]){
				for(auto h:e[i]){
					if(v[r].sub[h.fs]){
						continue;
					}
					if(vis[h.sc]){
						l.push_back(h.sc);
					}
					else{
						vis[h.sc]=1;
						auto z=s;
						for(auto &e:z){
							if(e==k){
								e=h.sc;
							}
						}
						int u=query(z)-pas;
						if(u==1){
							if(val==-1){
								val=0;
								for(auto e:ud){
									ans[e]=0;
								}
							}
							ans[h.sc]=1;
						}
						else if(u==-1){
							if(val==-1){
								val=1;
								for(auto e:ud){
									ans[e]=1;
								}
							}
							ans[h.sc]=0;
						}
						else{
							ud.push_back(h.sc);
						}
					}
				}
			}
		}
		if(val==-1){
			if(l.size()){
				auto h=l[0];
				auto z=s;
				for(auto &e:z){
					if(e==k){
						e=h;
					}
				}
				int u=query(z)-pas;
				if(u==0){
					val=ans[h];
				}
				else{
					val=1-ans[h];
				}
			}
			else{
				val=1;
			}
		}
		for(auto h:ud){
			ans[h]=val;
		}
		ans[k]=val;
	}
}tr;
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	int m=u.size();
	ans.resize(m);
	vis.resize(m);
	dsu.init(n);
	tr.init(n);
	e.resize(n);
	for(int i=0;i<m;i++){
		if(dsu.merge(u[i],v[i])){
			tr.add(u[i],v[i],i);
		}
		else{
			e[u[i]].push_back({v[i],i});
			e[v[i]].push_back({u[i],i});
		}
	}
	tr.pas=query(tr.s);
	tr.dfs(0,0,-1);
	vector<int> ret;
	for(int i=0;i<m;i++){
		if(ans[i]){
			ret.push_back(i);
		}
	}
	return ret;
}

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