Submission #417112

#	Time	Username	Problem	Language	Result	Execution time	Memory
417112		flappybird	Simurgh (IOI17_simurgh)	C++14	0 / 100	3059 ms	332 KiB

simurgh

#include "simurgh.h"

#include <bits/stdc++.h>
using namespace std;
typedef int ll;

#define MAX 1010
#define MAXS 10

ll N, M;
ll sp[MAX][MAXS];
ll depth[MAX];
vector<ll> adj[MAX], tree[MAX], back[MAX], ans[MAX];
vector<ll> query;
vector<ll> U, V;
ll vis[MAX];
bool ck[MAX];
ll isroyal[MAX];
ll treeres;
ll leaf[MAX];
ll adj2[MAX][MAX];
vector<ll> leafv;

void dfs(ll x = 0, ll p = -1, ll d = 0) {
	sp[x][0] = p;
	depth[x] = d;
	ll i;
	vis[x] = 1;
	for (i = 1; i < MAXS; i++) sp[x][i] = sp[sp[x][i - 1]][i - 1];
	for (auto v : adj[x]) if (!vis[v]) dfs(v, x, d + 1);
}
//{a, b}={c, d}인지 체크
bool chk(ll a, ll b, ll c, ll d) {
	if (a > b) swap(a, b);
	if (c > d) swap(c, d);
	return a == c && b == d;
}

ll getline(ll u, ll v) {
	ll i;
	for (i = 0; i < M; i++) if (chk(u, v, U[i], V[i])) return i;
	return -1;
}

ll getline(ll i) {
	return getline(U[i], V[i]);
}

ll lca(ll u, ll v) {
	if (depth[u] != depth[v]) {
		if (depth[u] < depth[v]) swap(u, v);
		ll i;
		for (i = MAXS - 1; i >= 0; i--) if (depth[sp[u][i]] >= depth[v]) u = sp[u][i];
	}
	if (u == v) return u;
	ll i;
	for (i = MAXS - 1; i >= 0; i--) if (sp[u][i] != sp[v][i]) u = sp[u][i], v = sp[v][i];
	return sp[v][0];
}

ll dis(ll u, ll v) {
	return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}

void erase(vector<ll>& v, ll a) {
	ll i;
	for (i = 0; i < v.size(); i++) if (v[i] == a) break;
	v.erase((v.begin() + i));
}

void getleaf(ll x = 0, ll p = -1) {
	ll c = 0;
	for (auto v : tree[x]) {
		if (v == p) continue;
		c = 1;
		getleaf(v, x);
	}
	if (!c) leaf[x] = 1, leafv.push_back(x);
}

ll p(ll r, ll x) {
	if (lca(r, x) == x) {
		for (auto v : adj[x]) {
			if (lca(v, r) == v && lca(x, v) == x) return v;
		}
	}
	else return sp[x][0];
}

//v is parent
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	N = n, M = u.size();
	ll i;
	for (i = 0; i < M; i++) adj[u[i]].push_back(v[i]), adj[v[i]].push_back(u[i]);
	dfs();
	for (i = 0; i < M; i++) {
		if (lca(u[i], v[i]) == u[i]) swap(u[i], v[i]);
		if (sp[u[i]][0] == v[i]) tree[u[i]].push_back(v[i]), tree[v[i]].push_back(u[i]);
		else back[u[i]].push_back(v[i]), back[v[i]].push_back(u[i]);
	}
	U = u, V = v;
	for (i = 0; i < N; i++) {
		for (auto v : tree[i]) {
			if (i < v) query.push_back(getline(i, v));
		}
	}
	treeres = count_common_roads(query);
	getleaf();
	bool c;
	while (1) {
		for (i = 1; i < N; i++) {
			c = true;
			if (leaf[i]) {
				if (back[i].empty()) {
					leaf[i] = 0;
					leaf[sp[i][0]] = 1;
					isroyal[i] = 1;
					continue;
				}
				c = false;
				for (auto x : back[i]) {
					if (lca(x, i) == x) {
						query.push_back(getline(i, x));
						map<ll, ll> mp;
						for (ll j = i; (j != x); j = sp[j][0]) {
							ll e = getline(j, sp[j][0]);
							erase(query, e);
							ll res = count_common_roads(query) - treeres;
							mp[j] = res;
							query.push_back(e);
						}
						erase(query, getline(i, x));
						set<ll> st;
						for (ll j = i; (j != x); j = sp[j][0]) st.insert(mp[j]);
						if (st.size() == 1) for (ll j = i; (j != x); j = sp[j][0]) isroyal[j] = 0;
						else {
							if (*st.begin() == -1) for (ll j = i; (j != x); j = sp[j][0]) isroyal[j] = -mp[j];
							else for (ll j = i; (j != x); j = sp[j][0]) isroyal[j] = 1 - mp[j];
						}
						leaf[i] = 0;
						leaf[x] = 1;
					}
					else if (leaf[x]) {
						ll l = lca(i, x);
						query.push_back(getline(i, x));
						map<ll, ll> mp;
						for (ll j = i; (j != l); j = sp[j][0]) {
							ll e = getline(j, sp[j][0]);
							erase(query, e);
							ll res = count_common_roads(query) - treeres;
							mp[j] = res;
							query.push_back(e);
						}
						for (ll j = x; (j != l); j = sp[j][0]) {
							ll e = getline(j, sp[j][0]);
							erase(query, e);
							ll res = count_common_roads(query) - treeres;
							mp[j] = res;
							query.push_back(e);
						}
						erase(query, getline(i, x));
						set<ll> st;
						for (ll j = i; (j != l); j = sp[j][0]) st.insert(mp[j]);
						for (ll j = x; (j != l); j = sp[j][0]) st.insert(mp[j]);
						if (st.size() == 1) {
							for (ll j = i; (j != x); j = sp[j][0]) isroyal[j] = 0;
							for (ll j = x; (j != l); j = sp[j][0]) isroyal[j] = 0;
						}
						else {
							if (*st.begin() == -1) {
								for (ll j = i; (j != l); j = sp[j][0]) isroyal[j] = -mp[j];
								for (ll j = x; (j != l); j = sp[j][0]) isroyal[j] = -mp[j];
							}
							else {
								for (ll j = i; (j != l); j = sp[j][0]) isroyal[j] = 1 - mp[j];
								for (ll j = x; (j != l); j = sp[j][0]) isroyal[j] = 1 - mp[j];
							}
						}
						leaf[i] = leaf[x] = 0;
						leaf[l] = 1;
					}
				}
			}
		}
		if (c) break;
	}
	vector<ll> ans;
	for (i = 0; i < N; i++) {
		for (auto x : adj[i]) {
			if (p(i, x) == i) continue;
			if (adj2[x][i]) continue;
			erase(query, getline(x, p(i, x)));
			ll e = getline(i, x);
			query.push_back(e);
			ll res = count_common_roads(query) + isroyal[getline(x, p(i, x))] - treeres;
			query.push_back(getline(x, p(i, x)));
			erase(query, e);
			adj2[i][x] = adj2[x][i] = 1;
			if (res == 1) ans.push_back(e);
		}
	}
	for (i = 1; i < N; i++) if (isroyal[i]) ans.push_back(getline(i, sp[i][0]));
	return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'void erase(std::vector<int>&, ll)':
simurgh.cpp:67:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for (i = 0; i < v.size(); i++) if (v[i] == a) break;
      |              ~~^~~~~~~~~~
simurgh.cpp: In function 'll p(ll, ll)':
simurgh.cpp:88:1: warning: control reaches end of non-void function [-Wreturn-type]
   88 | }
      | ^

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