Submission #779792

#	Time	Username	Problem	Language	Result	Execution time	Memory
779792		I_Love_EliskaM_	Simurgh (IOI17_simurgh)	C++14	51 / 100	216 ms	3036 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int a, int b) {return a+rng()%(b-a+1);}
#define all(x) x.begin(),x.end()


struct DSU {
	vector<int> p,sz;
	DSU(int n) {
		forn(i,n) p.pb(i), sz.pb(1);
	}
	int get(int u) {
		return p[u]==u?u:get(p[u]);
	}
	void uni(int u, int v) {
		u=get(u), v=get(v);
		if (u==v) return;
		if (sz[u]<sz[v]) swap(u,v);
		p[v]=u;
		sz[u]+=sz[v];
	}
};

const int N=500;
int adj[N][N];
int b[N][N];
int br[N*N];

vector<int> find_roads(int n, vector<int>u, vector<int>v) {
	int m=u.size();
	if (m==n-1) {
		vector<int> v; forn(i,m) v.pb(i);
		return v;
	}
	
	vector<int> z;
	set<int> s;
	forn(i,m) adj[u[i]][v[i]]=adj[v[i]][u[i]]=i;
	
	if (n>240) exit(0);

	vector<vector<int>> g(n);
	forn(i,m) {
		g[u[i]].pb(v[i]);
		g[v[i]].pb(u[i]);
	}

	map<int,int> was;
	forn(i,n) {
		
		DSU dsu(n);		
		vector<int> t;
		forn(j,m) {
			int x=u[j], y=v[j];
			if (x==i || y==i) continue;
			if (dsu.get(x)==dsu.get(y)) continue;
			dsu.uni(x,y);
			t.pb(j);
		}
		map<int,vector<int>> mp;
		for(auto&v:g[i]) {
			mp[dsu.get(v)].pb(adj[i][v]);
		}

		for(auto&it1:mp) {

			int c=it1.f;
			auto z=it1.s;
			auto q=t;
			for(auto&it2:mp) {
				if (it2.f==c) continue;
				q.pb(it2.s[0]);
			}
			vector<pi> v;
			int mx=0;
			int kurwa=1;
			for(auto&x:z) {
				if (was[x]) {
					if (kurwa && s.count(x)) {
						q.pb(x);
						int y=count_common_roads(q);
						q.pop_back();
						mx=max(mx,y);
						kurwa=0;
					}
					continue;
				}
				was[x]=1;
				q.pb(x);
				int y=count_common_roads(q);
				q.pop_back();
				v.pb({y,x});
				mx=max(mx,y);
			}
			for(auto&x:v) if (x.f==mx) s.insert(x.s);

		}

	}
	for(auto&x:s) z.pb(x);
	return z;

	///////////////

	if (m!=n*(n-1)/2) exit(0);


	for (int i=1; i<n; ++i) {
		vector<int> k;
		for(int j=1; j<n; ++j) {
			if (j==i) continue;
			k.pb(adj[0][j]);
		}
		vector<pi> t;
		int mx=0;
		forn(j,n) {
			if (j==i) continue;
			k.pb(adj[i][j]);
			int x=count_common_roads(k);
			k.pop_back();
			t.pb({x,j});
			mx=max(mx,x);
		}
		for(auto&x:t) if (x.f==mx) s.insert(adj[i][x.s]);
	}
	for(auto&x:s) z.pb(x);
	return z;

}

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