Submission #250223

#	Time	Username	Problem	Language	Result	Execution time	Memory
250223		srvlt	Simurgh (IOI17_simurgh)	C++14	30 / 100	136 ms	6904 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 = 243, m0 = 29000;
int N, M, used[n0], ch[m0], par[n0], sp[m0], same[m0];
int in[n0], out[n0], T, common;
vector <int> g[n0], V, U, query;

void dfs(int v) {
	used[v] = 1;
	in[v] = ++T;
	for (int i : g[v]) {
		int to = V[i] ^ U[i] ^ v;
		if (used[to]) continue;
		par[to] = i;
		query.pb(i);
		sp[i] =  1;
		dfs(to);
	}
	out[v] = T;
}

bool upper(int v, int u) {
	return in[v] <= in[u] && out[u] <= out[v];
}

void add(int x) {
	query.pb(x);
}

void del(int x) {
	for (int i = 0; i < SZ(query); i++) {
		if (query[i] == x) {
			query.erase(query.begin() + i);
			break;
		}
	}
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	memset(& ch, -1, sizeof(ch));
	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);
	dfs(0);
	vector <int> path;
	common = count_common_roads(query);
	for (int i = 0; i < M; i++) {
		if (sp[i]) continue;
		int a = v[i], b = u[i];
		if (upper(b, a)) swap(a, b);
		assert(upper(a, b));
		path.clear();
		while (b != a) {
			path.pb(par[b]);
			b = v[par[b]] ^ u[par[b]] ^ b;
		}
		add(i);
		for (int j : path) {
			del(j);
			int x = count_common_roads(query);
			if (x == common) {
				same[j] = 1;
			}	else {
				if (x == common - 1) {
					ch[i] = 0;
					ch[j] = 1;
				}
				if (x == common + 1) {
					ch[i] = 1;
					ch[j] = 0;
				}
			}
			add(j);
		}
		if (ch[i] == -1) ch[i] = 0;
		del(i);
		for (int j : path) {
			if (same[j]) ch[j] = ch[i];
			same[j] = 0;
		}
	}
	vector <int> res;
	for (int i = 0; i < M; i++) {
		if (ch[i] == -1) ch[i] = 1;
		if (ch[i] == 1) res.pb(i);
	}
	return res;
}

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