Submission #274843

#	Time	Username	Problem	Language	Result	Execution time	Memory
274843		junseo	Simurgh (IOI17_simurgh)	C++17	100 / 100	388 ms	9580 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define rmin(r, x) r = min(r, x);
#define rmax(r, x) r = max(r, x);
#define ends ' '
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0), cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int maxn = 505;
const int maxm = maxn * maxn;
 
int n, m, K;
pii pa[maxn];
bool visited[maxn], used[maxm];
int gold[maxm], k[maxm], h[maxn];
vector<pii> edge, adj[maxn], ch[maxn], bk[maxn], rbk[maxn];
vector<int> dfs_tree;
 
int count_common_roads(const vector<int>& r);
 
int count_k(vector<int> v, vector<pii> rep) {
	vector<int> q;
	for(auto [add, sub] : rep)	q.eb(add);
	int i = 0, j = 0;
	while(i < v.size()) {
		if(j < rep.size() && v[i] == rep[j].se) {
			++i;
			++j;
			continue;
		}
		q.eb(v[i++]);
	}
	return count_common_roads(q);
}
 
void dfs(int u, int p) {
	visited[u] = true;
	for(auto [v, i] : adj[u]) if(v != p && !used[i]) {
		used[i] = true;
		if(visited[v]) {
			bk[u].eb(i, ch[v].back().se);
			rbk[v].eb(u, i);
			continue;
		}
		dfs_tree.eb(i);
		ch[u].eb(v, i);
		pa[v] = {u, i};
		h[v] = h[u] + 1;
		dfs(v, u);
	}
}
 
void solve_tree(int u) {
	sort(all(rbk[u]), [&](pii a, pii b) { return h[a.fi] > h[b.fi]; });
	for(auto [v, i] : rbk[u]) {
		vector<int> tedge;
		bool all = true, no = true;
		while(v != u) {
			tedge.eb(pa[v].se);
			if(gold[tedge.back()] != -1)	all = false;
			else							no = false;
			v = pa[v].fi;
		}
		if(no)	continue;
 
		if(all) {
			int nk = n, xk = 0;
			for(auto j : tedge) {
				vector<pii> dum;	dum.eb(i, j);
				k[j] = count_k(dfs_tree, dum);
				rmin(nk, k[j]);
				rmax(xk, k[j]);
			}
			if(nk != xk) {
				gold[i] = nk - (K - 1);
				for(auto j : tedge)		gold[j] = (nk == k[j]);
			}
			else {
				if(nk == K - 1)	{
					for(auto j : tedge)	gold[j] = true;
					gold[i] = false;
				}
				else	for(auto j : tedge)	gold[j] = false;
			}
		}
		else {
			for(auto j : tedge) if(gold[j] != -1) {
				vector<pii> dum;	dum.eb(i, j);
				gold[i] = count_k(dfs_tree, dum) - K + gold[j];
				break;
			}
			for(auto j : tedge) if(gold[j] == -1) {
				vector<pii> dum;	dum.eb(i, j);
				gold[j] = K + gold[i] - count_k(dfs_tree, dum);
			}
		}
		
	}
	for(auto [v, i] : ch[u])	solve_tree(v);
}
 
void solve_back(vector<pii> e, int l, int r, int cnt) {
	// count_k = K - S(gold[sub]) + S(gold[add])
	// S(gold[add]) = count_k - K + S(gold[sub])
	if(l > r)	return;
	if(cnt == 0) {
		for(auto [add, sub] : e)	gold[add] = false;
		return;
	}
	if(cnt == r - l + 1) {
		for(auto [add, sub] : e)	gold[add] = true;
		return;
	}
	
	int mid = l + r >> 1;
	vector<pii> t;
	for(int i = mid + 1; i <= r; ++i) {
		t.eb(e.back());
		e.pop_back();
	}
	reverse(all(t));
	int ret = count_k(dfs_tree, e) - K;
	for(auto [add, sub] : e)	ret += gold[sub];
 
	solve_back(e, l, mid, ret);
	solve_back(t, mid + 1, r, cnt - ret);
}
 
std::vector<int> find_roads(int _n, std::vector<int> u, std::vector<int> v) {
	n = _n, m = u.size();
	for(int i = 0; i < m; ++i) {
		edge.eb(u[i], v[i]);
		adj[u[i]].eb(v[i], i);
		adj[v[i]].eb(u[i], i);
	}
	dfs(0, -1);
	sort(all(dfs_tree));
 
	K = count_k(dfs_tree, vector<pii>());
	memset(gold, -1, sizeof(gold));
	solve_tree(0);
	
	for(int i = 0; i < n; ++i) if(!bk[i].empty()) {
		sort(all(bk[i]), [](pii a, pii b) { return a.se < b.se; });
		vector<pii> v;
		for(auto t : bk[i]) if(gold[t.fi] == -1) v.eb(t);
		if(!v.empty()) {
			int cnt = count_k(dfs_tree, v) - K;
			for(auto [add, sub] : v)	cnt += gold[sub];
			solve_back(v, 0, v.size() - 1, cnt);
		}
	}
 
	vector<int> ans;
	for(int i = 0; i < m; ++i)	if(gold[i])	ans.eb(i);
	return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'int count_k(std::vector<int>, std::vector<std::pair<int, int> >)':
simurgh.cpp:33:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  while(i < v.size()) {
      |        ~~^~~~~~~~~~
simurgh.cpp:34:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   if(j < rep.size() && v[i] == rep[j].se) {
      |      ~~^~~~~~~~~~~~
simurgh.cpp: In function 'void solve_back(std::vector<std::pair<int, int> >, int, int, int)':
simurgh.cpp:123:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  123 |  int mid = l + r >> 1;
      |            ~~^~~

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