Submission #1199069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199069		dosts	Simurgh (IOI17_simurgh)	C++20	30 / 100	62 ms	3612 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
//#define int long long
#define pii pair<int,int> 
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " << 
#define all(x) x.begin(),x.end()
using namespace std;

struct DSU {
	int n;
	vi dad,sz;
	vector<vi> v;

	DSU(int nn) {
		n = nn;
		dad.resize(n);
		v.resize(n);
		sz.assign(n,1);
		for (int i = 0;i<n;i++) v[i].push_back(i);
		iota(all(dad),0ll);
	}
	int find(int x) {
		if (x == dad[x]) return x;
		return dad[x] = find(dad[x]);
	}
	bool unite(int x,int y) {
		int a = find(x),b = find(y);
		if (a == b) return false;
		if (sz[a] > sz[b]) swap(a,b);
		dad[a] = b;
		sz[b]+=sz[a];
		for (auto it : v[a]) v[b].push_back(it);
		v[a].clear();
		sz[a] = 0;
		return true;
	}
};

int cache[501][501],got[501][501];
int oldie;

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	int m = u.size();
	DSU dsu(n);
	vi mst;
	memset(got,-1,sizeof got);
	memset(cache,-1,sizeof cache);
	for (int i = 0;i<m;i++) {
		got[u[i]][v[i]] = got[v[i]][u[i]] = i;
		if (dsu.unite(u[i],v[i])) {
			mst.push_back(i);
		}
	}
	assert(mst.size() == n-1);
	oldie = count_common_roads(mst);
	set<int> ans;
	for (int i = 0;i<n-1;i++) {
		int road = mst[i];
		DSU dsu2(n);
		vi mstt;
		for (int j = 0;j<n-1;j++) {
			if (j != i) {
				dsu2.unite(u[mst[j]],v[mst[j]]);
				mstt.push_back(mst[j]);
			}
		}
		int found = 0;
		int bad = 0,good = 0;
		for (int A : dsu2.v[dsu2.find(u[mst[i]])]) {
			if (found) break;
			for (int B : dsu2.v[dsu2.find(v[mst[i]])]) {
				if (found) break;
				int a = A,b = B;
				if (a > b) swap(a,b);
				if (got[a][b] == -1) continue;
				if (cache[a][b] != -1) {
					found = 1;
					mstt.push_back(got[a][b]);
					int nw = count_common_roads(mstt);
					if (nw > oldie) bad = 1;
					else if (nw < oldie) good = 1;
					else {
						if (cache[a][b] == 0) bad = 1;
						else good = 1;
					}
					mstt.pop_back();
					break;
				}
			}
		}
		if (!found) {
			for (int A : dsu2.v[dsu2.find(u[mst[i]])]) {
				for (int B : dsu2.v[dsu2.find(v[mst[i]])]) {
					int a = A,b = B;
					if (a > b) swap(a,b);
					if (got[a][b] == -1) continue;
					mstt.push_back(got[a][b]);
					int nw = count_common_roads(mstt);
					if (nw > oldie) {
						bad = 1;
						ans.insert(got[a][b]);
						cache[a][b] = 1;
					}
					else if (nw < oldie) {
						good = 1;
						cache[a][b] = 0;
					}
					mstt.pop_back();
				}
			}
		}
		if ((!bad && !good)) good = 1;
		if (good) {
			cache[u[mst[i]]][v[mst[i]]] = 1;
			ans.insert(mst[i]);
			for (int A : dsu2.v[dsu2.find(u[mst[i]])]) {
				for (int B : dsu2.v[dsu2.find(v[mst[i]])]) {
					int a = A,b = B;
					if (a > b) swap(a,b);
					if (got[a][b] == -1) continue;
					if (cache[a][b] != -1) continue;
					mstt.push_back(got[a][b]);
					int nw = count_common_roads(mstt);
					if (nw == oldie) {
						ans.insert(got[a][b]);
						cache[a][b] = 1;
					}
					else cache[a][b] = 0;
					mstt.pop_back();
				}
			}	
		}
		else {
			for (int A : dsu2.v[dsu2.find(u[mst[i]])]) {
				for (int B : dsu2.v[dsu2.find(v[mst[i]])]) {
					int a = A,b = B;
					if (a > b) swap(a,b);
					if (got[a][b] == -1) continue;
					if (cache[a][b] != -1) continue;
					mstt.push_back(got[a][b]);
					int nw = count_common_roads(mstt);
					if (nw == oldie) cache[a][b] = 0;
					else {						
						ans.insert(got[a][b]);
						cache[a][b] = 1;
					}
					mstt.pop_back();
				}
			}			
		}
	}
	vi vv;
	for (auto it : ans) vv.push_back(it);
	return vv;
}

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