제출 #250695

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
250695		srvlt	Simurgh (IOI17_simurgh)	C++14	100 / 100	1098 ms	7352 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 = 503, m0 = 125000;
int N, M, used[n0], par[n0], ch[m0], same[m0], ep[m0];
int in[n0], out[n0], T, S;
vector <int> g[n0], V, U, query, back[n0];
set <int> st;

void add(int x) {
	st.insert(x);
}

void del(int x) {
	st.erase(x);
}

bool ex(int x) {
	return st.find(x) != st.end();
}

int ask() {
	query.clear();
	for (int i : st) query.pb(i);
	return count_common_roads(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;
		add(i);
		dfs(to);
	}
	out[v] = T;
}

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

bool cmp(const int & x, const int & y) {
	if (x == y) return false;
	return upper(ep[y], ep[x]);
}

int get(int v, int k) {
	int u = v, res = S;
	for (int i = 0; i <= k; i++) {
		int j = back[v][i];
		int to = V[j] ^ U[j] ^ v;
		add(j), del(par[u]);
		if (ch[par[u]] == 1) {
			res--;
		}
		u = to;
	}
	res = ask() - res;
	u = v;
	for (int i = 0; i <= k; i++) {
		int j = back[v][i];
		int to = V[j] ^ U[j] ^ v;
		del(j), add(par[u]);
		u = to;
	}
	return res;
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	N = n, M = SZ(u), V = v, U = u;
	for (int i = 0; i < M; i++)
		g[v[i]].pb(i), g[u[i]].pb(i);
	memset(& ch, -1, sizeof(ch));
	par[0] = -1;
	dfs(0);
	vector <int> path;
	S = ask();
	for (int i = 0; i < M; i++) {
		if (ex(i)) continue;
		int a = v[i], b = u[i];
		if (upper(b, a)) swap(a, b);
		assert(upper(a, b));
		int ok = 0;
		path.clear();
		while (b != a) {
			path.pb(par[b]);
			if (ch[par[b]] == -1) ok = 1;
			b = v[par[b]] ^ u[par[b]] ^ b;
		}
		if (!ok) continue;
		add(i);
		for (int j : path) {
			if (ch[i] != -1 && ch[j] != -1) continue;
			del(j);
			int x = ask();
			if (x == S) {
				same[j] = 1;
				if (ch[j] != -1) ch[i] = ch[j];
			}	else if (x == S + 1) {
				ch[i] = 1;
				ch[j] = 0;
			}	else {
				ch[i] = 0;
				ch[j] = 1;
			}
			add(j);
		}
		del(i);
		if (ch[i] == -1) ch[i] = 0;
		for (int j : path) {
			if (same[j]) ch[j] = ch[i];
			same[j] = 0;
		}
	}
	for (int i = 0; i < M; i++)
		if (ex(i) && ch[i] == -1) ch[i] = 1;
	for (int i = 0; i < N; i++) {
		for (int j : g[i]) {
			if (!ex(j)) {
				int to = v[j] ^ u[j] ^ i;
				if (upper(to, i)) {
					ep[j] = to;
					back[i].pb(j);
				}
			}
		}
		sort(all(back[i]), cmp);
		int cur = -1, have = 0;
		while (true) {
			int l = cur, r = SZ(back[i]);
			while (l < r - 1) {
				int mid = l + r >> 1;
				if (get(i, mid) > have) {
					r = mid;
				}	else {
					l = mid;
				}
			}
			cur = r;
			if (r < SZ(back[i])) {
				ch[back[i][r]] = 1;
				have++;
			}	else break;
		}
	}
	vector <int> res;
	for (int i = 0; i < M; i++) {
		if (ch[i] == -1) ch[i] = 0;
		if (ch[i] == 1) res.pb(i);
	}
	return res;
}

컴파일 시 표준 에러 (stderr) 메시지

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:146:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     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