Submission #1011795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011795		jcelin	Simurgh (IOI17_simurgh)	C++14	0 / 100	77 ms	3132 KiB

simurgh

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

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

#define X first
#define Y second
#define PB push_back
#define PPB pop_back
#define all(x) (x).begin(), (x).end() 

const int MAXN = 1e6 + 7;


struct uf{
	int par[MAXN], sz[MAXN];
	
	void res(int n){
		for(int i=0; i<n; i++) par[i] = i, sz[i] = 1;
	}
	
	int find(int x){
		return par[x] == x ? x : par[x] = find(par[x]);
	}
	
	bool unite(int a, int b){
		a = find(a), b = find(b);
		if(a == b) return 0;
		if(sz[a] < sz[b]) swap(a, b);
		par[b] = a;
		sz[a] += sz[b];
		return 1;
	}
}s;



/*
int count_common_roads(vi r){
	
}
*/

vi find_roads(int n, vi u, vi v){
	vi ans;
	int m = u.size();
	ans.clear();
	for(int i=0; i<n; i++){
		if((int)ans.size() + 1 == n) break;	
		vi x, y;
		for(int j=0; j<m; j++){
			if(u[j] == i or v[j] == i) x.PB(j);
			else y.PB(j);
		}
		
		if(x.size() == 1){
			ans.PB(x[0]);
			continue;
		}
		
		s.res(n);
		vi toq;
		for(auto &t : y) if(s.unite(u[t], v[t])) toq.PB(t);
		
		
		vii ret;
		for(auto &t : x){
			toq.PB(t);
			int vl = count_common_roads(toq);
			toq.PPB();
			ret.PB({vl, t});
		}
		sort(all(ret));
		int vl = ret.back().X;
		for(auto &t : ret) if(t.X == vl) ans.PB(t.Y);
		
		sort(all(ans));
		ans.erase(unique(all(ans)), ans.end());
	}
	return ans;
}

/*
void solve(){
	int n, m;
	cin >> n >> m;
	vi x, y;
	for(int i=1; i<=m; i++){
		int a, b;
		cin >> a >> b;
		x.PB(a);
		y.PB(b);
	}
	find_roads(n, m, x, y);
	
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solve();
	return 0;
}
*/

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