Submission #417601

#	Time	Username	Problem	Language	Result	Execution time	Memory
417601		flappybird	Simurgh (IOI17_simurgh)	C++14	30 / 100	2689 ms	5696 KiB

simurgh

//도배하는거 아니에요!!!
#include "simurgh.h"

#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
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;
	assert(0);
}

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));
}

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];
}

ll a(ll i) {
	if (sp[U[i]][0] == V[i]) return U[i];
	else return V[i];
}

//v is parent
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	ll cnt = 0;
	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));
		}
	}
	cnt++;
	assert(cnt <= 29998);
	treeres = count_common_roads(query);
	ll k, m;
	for (k = 0; k < N; k++) isroyal[k] = -1;
	for (k = 0; k < N; k++) {
		for (m = 0; m < back[k].size(); k++) {
			ll v1 = k, v2 = back[k][m];
			ll l = lca(v1, v2);
			ll x = -1;
			for (i = v1; i != l; i = sp[i][0]) {
				if (isroyal[i] != -1) {
					x = i;
					break;
				}
			}
			for (i = v2; i != l; i = sp[i][0]) {
				if (isroyal[i] != -1) {
					x = i;
					break;
				}
			}
			if (x != -1) {
				query.push_back(getline(v1, v2));
				erase(query, getline(x, sp[x][0]));
				cnt++;
				assert(cnt <= 29998);
				ll r0 = treeres - count_common_roads(query) - isroyal[x];
				query.push_back(getline(x, sp[x][0]));
				for (i = v1; i != l; i = sp[i][0]) {
					if (isroyal[i] != -1) continue;
					erase(query, getline(i, sp[i][0]));
					cnt++;
					assert(cnt <= 29998);
					ll res = treeres - count_common_roads(query);
					if (res != r0) isroyal[i] = 1;
					else isroyal[i] = 0;
					query.push_back(getline(i, sp[i][0]));
				}
				for (i = v2; i != l; i = sp[i][0]) {
					if (isroyal[i] != -1) continue;
					erase(query, getline(i, sp[i][0]));
					cnt++;
					assert(cnt <= 29998);
					ll res = treeres - count_common_roads(query);
					if (res != r0) isroyal[i] = 1;
					else isroyal[i] = 0;
					query.push_back(getline(i, sp[i][0]));
				}
				erase(query, getline(v1, v2));
			}
			else {
				query.push_back(getline(v1, v2));
				map<ll, ll> mp;
				for (ll j = v1; (j != l); j = sp[j][0]) {
					ll e = getline(j, sp[j][0]);
					erase(query, e);
					cnt++;
					assert(cnt <= 29998);
					ll res = count_common_roads(query) - treeres;
					mp[j] = res;
					query.push_back(e);
				}
				for (ll j = v2; (j != l); j = sp[j][0]) {
					ll e = getline(j, sp[j][0]);
					erase(query, e);
					cnt++;
					assert(cnt <= 29998);
					ll res = count_common_roads(query) - treeres;
					mp[j] = res;
					query.push_back(e);
				}
				erase(query, getline(v1, v2));
				set<ll> st;
				for (ll j = v1; (j != l); j = sp[j][0]) st.insert(mp[j]);
				for (ll j = v2; (j != l); j = sp[j][0]) st.insert(mp[j]);
				if (st.size() == 1) {
					if (*st.begin() >= 0) {
						for (ll j = v1; (j != l); j = sp[j][0]) isroyal[j] = 0;
						for (ll j = v2; (j != l); j = sp[j][0]) isroyal[j] = 0;
					}
					else {
						for (ll j = v1; (j != l); j = sp[j][0]) isroyal[j] = 1;
						for (ll j = v2; (j != l); j = sp[j][0]) isroyal[j] = 1;
					}
				}
				else {
					if (*st.begin() == -1) {
						for (ll j = v1; (j != l); j = sp[j][0]) isroyal[j] = -mp[j];
						for (ll j = v2; (j != l); j = sp[j][0]) isroyal[j] = -mp[j];
					}
					else {
						for (ll j = v1; (j != l); j = sp[j][0]) isroyal[j] = 1 - mp[j];
						for (ll j = v2; (j != l); j = sp[j][0]) isroyal[j] = 1 - mp[j];
					}
				}
			}
		}
	};
	for (i = 0; i < N; i++) if (isroyal[i]) isroyal[i] = 1;
	assert(cnt <= 3 * N);
	vector<ll> ans;
	for (i = 1; i < N; i++) if (isroyal[i] == 1) ans.push_back(getline(i, sp[i][0]));
	assert(ans.size() == treeres);
	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);
			cnt++;
			assert(cnt <= 29998);
			ll res = count_common_roads(query) + isroyal[a(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);
		}
	}
	sort(ans.begin(), ans.end());
	ans.erase(unique(ans.begin(), ans.end()), ans.end());
	return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'void erase(std::vector<int>&, ll)':
simurgh.cpp:73:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for (i = 0; i < v.size(); i++) if (v[i] == a) break;
      |              ~~^~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:115:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |   for (m = 0; m < back[k].size(); k++) {
      |               ~~^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from simurgh.cpp:5:
simurgh.cpp:212:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  212 |  assert(ans.size() == treeres);
      |         ~~~~~~~~~~~^~~~~~~~~~
simurgh.cpp: In function 'll p(ll, ll)':
simurgh.cpp:84:1: warning: control reaches end of non-void function [-Wreturn-type]
   84 | }
      | ^

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