Submission #249865

#	Time	Username	Problem	Language	Result	Execution time	Memory
249865		srvlt	Simurgh (IOI17_simurgh)	C++14	0 / 100	1 ms	640 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n0 = 53, m0 = 1300;
int N, M, par[n0], used[n0], ch[m0], h[n0], common;
vector <int> g[n0], V, U, cur;
set <int> st1, st2;

void add(int x) {
	st1.insert(x), st2.erase(x);
}

void del(int x) {
	st1.erase(x), st2.insert(x);
}

void dfs(int v, bool flag) {
	if (v == 0) par[v] = -1;
	used[v] = 1;
	for (int i : g[v]) {
		int to = V[i] ^ U[i] ^ v;
		if (used[to] || (flag && st1.find(i) == st1.end())) continue;
		par[to] = i;
		h[to] = h[v] + 1;
		if (!flag)
			add(i);
		dfs(to, flag);
	}
}

int ask() {
	cur.clear();
	for (int i : st1) cur.pb(i);
	return count_common_roads(cur);
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	for (int i = 0; i < m0; i++) ch[i] = 2;
	N = n, M = u.size(), V = v, U = u;
	for (int i = 0; i < M; i++) {
		g[v[i]].pb(i), g[u[i]].pb(i);
		st2.insert(i);
	}
	dfs(0, false);
	common = ask();
	vector <int> path;
	while (!st2.empty()) {
		path.clear();
		int i = *st2.begin();
		int a = v[i], b = u[i];
		if (h[a] > h[b]) swap(a, b);
		int bad = 0;
		while (b != a) {
			if (par[b] == -1) {
				st2.erase(i);
				bad = 1;
				break;
			}
			path.pb(par[b]);
			b = v[par[b]] ^ u[par[b]] ^ b;
		}
		if (bad) continue;
		add(i);
		int ind = -1;
		for (int j : path) {
			if (ch[j] == 1) continue;
			del(j);
			int x = ask();
			add(j);
			if (x == common + 1) {
				common++;
				ch[i] = 1;
				ind = j;
				break;
			}
		}
		if (ch[i] == 2) ch[i] = 3;
		if (ch[i] == 1) {
			assert(ind != -1);
			ch[ind] = 3;
			del(ind);
			st2.erase(ind);
			memset(& used, 0, sizeof(used));
			dfs(0, true);
		}	else {
			del(i);
			st2.erase(i);
		}
	}
	assert(ask() == n - 1);
	return cur;
}

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