Submission #1028859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028859		DorostWef	Simurgh (IOI17_simurgh)	C++17	0 / 100	1 ms	348 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;
typedef pair <int, int> pii;
#define F first
#define S second
const int N = 506, M = N * N;
set <int> st;
vector <pii> g[N];
bool vis[N];
int h[N], par[N];
int a[M], b[M];
int w[M];
vector <int> tree;
int p[N], sz[N];
int d[N];
int nn;
bool ff[M];

void asser (bool f) {
	if (!f) {
		while (true)
			cerr << "wef" << endl;
	}
}

int get_par (int v) {
	if (p[v] == v)
		return v;
	return p[v] = get_par (p[v]);
}

bool merge(int u, int v) {
	u = get_par (u);
	v = get_par (v);
	if (u == v)
		return false;
	if (sz[u] > sz[v])
		swap (u, v);
	p[u] = v;
	return true;
}

void clear() {
	for (int i = 0; i < N; i++) {
		p[i] = i;
		sz[i] = 1;
	}
}

int cc = 0;

int askt () {
	cc++;
	if (cc >= 8000)
		exit (cc);
	vector <int> wef;
	for (int x : st)
		wef.push_back(x);
	return count_common_roads(wef);
}

void dfs (int v) {
	vis[v] = true;
	for (pii p : g[v]) {
		int u = p.F;
		if (!vis[u]) {
			h[u] = h[v] + 1;
			par[u] = p.S;
			dfs (u);
			tree.push_back (p.S);
			st.insert (p.S);
		}
	}
}

int askj (vector <int> wef) {
	clear();
	for (int i : wef) {
		asser (merge (a[i], b[i]));
	}
	int k = 0;
	for (int i : tree) {
		if (merge (a[i], b[i])) {
			wef.push_back (i);
			k += w[i];
		}
	}
	asser (wef.size() == nn - 1);
	int wefwef = count_common_roads (wef) - k;
	return wefwef;
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	nn = n;
	int m = (int)u.size();
	for (int i = 0; i < m; i++) {
		w[i] = -1;
		a[i] = u[i];
		b[i] = v[i];
		g[a[i]].push_back(make_pair (b[i], i));
		g[b[i]].push_back(make_pair (a[i], i));
	}
	dfs (0);
	int k = askt();
	for (int i = 0; i < m; i++) {
		if (abs (h[a[i]] - h[b[i]]) >= 2) {
			if (h[a[i]] < h[b[i]])
				swap (a[i], b[i]);
			vector <int> alo;
			int vv = a[i];
			bool f = false;
			int h = -1;
			while (vv != b[i]) {
				if (w[par[vv]] == -1)
					f = true;
				if (w[par[vv]] != -1) 
					h = par[vv];
				alo.push_back (par[vv]);
				vv = a[par[vv]] ^ b[par[vv]] ^ vv;
			}
			if (!f)
				continue;
			if (h != -1) {
				st.insert(i);
				st.erase (vv);
				int o = askt();
				o = o - (k - w[vv]);
				st.insert (vv);
				for (int few : alo) {
					if (w[few] == -1) {
						st.erase (few);
						w[few] = k - (askt() - o);
						st.insert (few);
					}
				}
				st.erase(i);
			} else {
				st.insert (i);
				int mx = k;
				vector <int> what;
				for (int few : alo) {
					st.erase (few);
					int wef = askt();
					mx = max (mx, wef);
					what.push_back(wef);
					st.insert (few);
				}
				st.erase (i);
				for (int j = 0; j < (int)alo.size(); j++) {
					w[alo[j]] = mx - what[j];
				}
			}
		}
	}
	for (int i : tree) {
		if (w[i] == -1)
			w[i] = 1;
	}
	for (int i = 0; i < n; i++) {
		vector <int> adj;
		for (pair <int, int> p : g[i])
			adj.push_back (p.S);
		d[i] = askj (adj);
	}
	vector <int> ans;
	for (int i = 0; i < n - 1; i++) {
		int x = -1;
		for (int j = 0; j < n; j++) {
			if (d[j] == 1) {
				x = j;
			}
		}
		asser (x != -1);
		vector <int> adj;
		for (pair <int, int> p : g[x]) {
			if (!ff[p.S]) 
				adj.push_back (p.S);
		}
		asser (adj.size() >= 1);
		int l = -1, r = (int)adj.size() - 1;
		while (r - l > 1) {
			int mid = (l + r) >> 1;
			vector <int> wef;
			for (int j = 0; j <= mid; j++) {
				wef.push_back(adj[j]);
			}
			if (askj(wef) == 1) {
				r = mid;
			} else {
				l = mid;
			}
		}
		ff[adj[r]] = true;
		ans.push_back (adj[r]);
		d[a[adj[r]]]--;
		d[b[adj[r]]]--;
	}
//	for (int x : ans)
//		cout << x << ' ';
//	cout << '\n';
	if (count_common_roads (ans) != n - 1)
		asser (false);
	return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'int askj(std::vector<int>)':
simurgh.cpp:90:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   90 |  asser (wef.size() == nn - 1);
      |         ~~~~~~~~~~~^~~~~~~~~

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