Submission #299796

#	Time	Username	Problem	Language	Result	Execution time	Memory
299796		errorgorn	Simurgh (IOI17_simurgh)	C++14	51 / 100	236 ms	3072 KiB

simurgh

#include "simurgh.h"

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<int,int>
#define fi first
#define se second

#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

ii mp(int i,int j){
	if (i<j) return ii(i,j);
	else return ii(j,i);
}

int n,m;
ii edges[300005];
vector<ii> al[255];

bool bridge[300005];
bool tested[300005];
bool good[300005];

int in[300005];
int low[300005];

int TIME=1;
void dfs(int i,int p){
	in[i]=low[i]=TIME++;
	
	for (auto &it:al[i]){
		if (!in[it.fi]){
			dfs(it.fi,i);
			low[i]=min(low[i],low[it.fi]);
			
			if (in[i]<low[it.fi]){
				bridge[it.se]=true;
			}
		}
		else if (it.fi!=p){
			low[i]=min(low[i],in[it.fi]);
		}
	}
}

struct UFDS{
	int p[255];
	
	void reset(){
		rep(x,0,255) p[x]=x;
	}
	
	int parent(int i){
		if (p[i]==i) return i;
		else return p[i]=parent(p[i]);
	}
	
	bool unions(int i,int j){
		i=parent(i),j=parent(j);
		
		if (i==j) return false;
		p[i]=j;
		return true;
	}
	
} ufds;

std::vector<int> find_roads(int N, std::vector<int> u, std::vector<int> v) {
	n=N,m=sz(u);
	
	rep(x,0,m){
		edges[x]=ii(u[x],v[x]);
		al[u[x]].push_back(ii(v[x],x));
		al[v[x]].push_back(ii(u[x],x));
	}
	
	//dfs(0,-1);
	
	rep(node,0,n){
		ufds.reset();
		
		vector<ii> child;
		
		for (auto &it:al[node]) child.push_back(it);
		
		vector<int> cand;
		rep(x,0,m){
			if (edges[x].fi==node || edges[x].se==node) continue;
			
			if (ufds.unions(edges[x].fi,edges[x].se)){
				cand.push_back(x);
			}
		}
		
		map<int,vector<int> > neigh;
		
		for (auto &it:child){
			int temp=ufds.parent(it.fi);
			
			if (!neigh.count(temp)) neigh[temp]=vector<int>();
			neigh[temp].push_back(it.se);
		}
		
		for (auto &it:neigh){
			vector<int> cand2=cand;
			
			for (auto &it2:neigh) if (it2!=it){
				cand2.push_back(it2.se[0]);
			}
			
			int val=-1;
			vector<int> proc;
			
			bool has_cmp=false;
			for (auto &iter:it.se){
				if (tested[iter]){
					if (!good[iter]) continue;
					if (has_cmp) continue;
					has_cmp=true;
				}
				
				cand2.push_back(iter);
				
				int temp=count_common_roads(cand2);
				if (temp>val) val=temp,proc.clear();
				if (temp==val) proc.push_back(iter);
				
				cand2.pop_back();
				
				tested[iter]=true;
			}
			
			for (auto &it:proc) good[it]=true;
		}
	}
	
	vector<int> ans;
	rep(x,0,300005) if (good[x]) ans.push_back(x);
	return ans;
}

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