제출 #415110

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
415110		Kevin_Zhang_TW	Simurgh (IOI17_simurgh)	C++17	100 / 100	480 ms	6628 KiB

simurgh

#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// My bug list :
// integer overflow
// 0based, 1based forgotten
// index out of bound
// n, m, i, j typo
// some cases are missing

int mqcnt;

int qry(vector<int> r) { ++mqcnt; return count_common_roads(r); }

const int MAX_N = 505;

int id[MAX_N][MAX_N], state[MAX_N][MAX_N];

int dep[MAX_N], pa[MAX_N], n;

bool vis[MAX_N], on_tree[MAX_N][MAX_N];

vector<pair<int,int>> te, alle;
vector<int> tid;

void dfs(int x, int lst) {
	pa[x] = lst;
	dep[x] = dep[lst] + 1;

	vis[x] = true;
	for (int i = 0;i < n;++i) if (!vis[i] && id[x][i] != -1) {
		dfs(i, x);
		te.pb(i, x);
		tid.pb(id[i][x]);
		on_tree[i][x] = on_tree[x][i] = true;
	}
}
pair<vector<int>, vector<int>> get_path(int a, int b) {
	vector<int> l, r;
	while (a != b) {
		if (dep[a] > dep[b]) {
			l.pb(a);
			a = pa[a];
		}
		else {
			r.pb(b);
			b = pa[b];
		}
	}
	return {l, r};
}
vector<int> operator - (vector<int> a, int v) { assert(count(AI(a), v)); a.erase(find(AI(a), v)); return a; }
vector<int> operator + (vector<int> a, int v) { a.pb(v); return a; }

struct dsu {
	vector<int> g, sz;
	int F(int i) { return i == g[i] ? i : g[i] = F(g[i]); }
	bool M(int a, int b) { 
		a = F(a), b = F(b);
		if (a == b) return false;
		if (sz[a] < sz[b]) swap(a, b);
		return g[b] = a, sz[a] += sz[b], true;
	}
	dsu(int n) { g.resize(n+10), sz.resize(n+10, 1); iota(AI(g), 0); }
};

int get_cnt(vector<int> part) {
	vector<int> r = part;
	dsu D(n);
	for (int id : part) {
		auto [a, b] = alle[id];
		D.M(a, b);
	}
	int sum = 0;
	for (auto [a, b] : te)
		if (D.M(a, b)) {
			r.pb(id[a][b]);
			sum += state[a][b];
		}
	assert(r.size() == n-1);
	return qry(r) - sum;
}

void bs(vector<int> part, int sum) {
	if (sum == 0) return;
	if (part.size() == 1) {
		auto [a, b] = alle[ part[0] ];
		state[a][b] = state[b][a] = 1;
		return;
	}
	int mid = part.size()/2;
	vector<int> l, r;
	for (int i = 0;i < part.size();++i)
		(i<mid?l:r).pb(part[i]);

	int cl = get_cnt(l);
	bs(l, cl);
	bs(r, sum-cl);
}

void solve(int h) {
	vector<int> cur;
	for (int i = 0;i < n;++i) if (id[h][i] != -1 && state[i][h] == -1)
		cur.pb(id[h][i]);
	if (cur.empty()) return;
	bs(cur, get_cnt(cur));
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	int m = u.size();
	::n = n;
	for (int i = 0;i < n;++i) fill(id[i], id[i] + n, -1);
	for (int i = 0;i < m;++i) {
		int a = u[i], b = v[i];
		alle.pb(a, b);
		id[a][b] = id[b][a] = i;
		state[a][b] = state[b][a] = -1;
	}

	dfs(0, 0);

	int tsum = qry(tid);

	for (int i = 0;i < m;++i) {
		auto [a, b] = alle[i];
		if (on_tree[a][b]) continue;
		auto [l, r] = get_path(a, b);
		int cnt = 0;
		vector<int> not_sure, sure;
		for (int u : l)
			if (state[u][ pa[u] ] == -1)
				not_sure.pb(id[u][pa[u]]);
			else sure.pb(id[u][pa[u]]);
		for (int u : r)
			if (state[u][ pa[u] ] == -1)
				not_sure.pb(id[u][pa[u]]);
			else sure.pb(id[u][pa[u]]);

		if (not_sure.empty()) continue;

		vector<int> small, same, big;

		for (int eid : not_sure) {
			int qv = qry( (tid - eid) + id[a][b] );
			if (qv > tsum) big.pb(eid);
			if (qv == tsum) same.pb(eid);
			if (qv < tsum) small.pb(eid);
		}

		int cur_v = -1;
		if (small.size()) cur_v = 0;
		if (big.size()) cur_v = 1;
		if (cur_v == -1 && same.size() == l.size() + r.size())
			cur_v = 0;

		if (cur_v == -1 && sure.size()) {
			int qv = qry( (tid - sure[0]) + id[a][b] );
			auto [x, y] = alle[ sure[0] ];
			if (qv > tsum) cur_v = 1;
			if (qv == tsum) cur_v = state[x][y];
			if (qv < tsum) cur_v = 0;
		}

		for (int eid : big) {
			auto [x, y] = alle[eid];
			state[x][y] = state[y][x] = cur_v - 1;
		}

		for (int eid : small) {
			auto [x, y] = alle[eid];
			state[x][y] = state[y][x] = cur_v + 1;
		}

		for (int eid : same) {
			auto [x, y] = alle[eid];
			state[y][x] = state[x][y] = cur_v;
		}

		state[b][a] = state[a][b] = cur_v;
	}

	for (auto [a, b] : te) {
		if (state[a][b] == -1)
			state[a][b] = state[b][a] = 1;
	}

	assert(mqcnt <= n + n);

	for (int i = 0;i < n;++i) solve(i);

	vector<int> res;
	for (int i = 0;i < n;++i) for (int j = i+1;j < n;++j) {
		if (id[i][j] == -1) continue;
		if (state[i][j] == 1) res.pb(id[i][j]);
		DE(i, j, state[i][j]);
	}
	return res;
}

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

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from simurgh.cpp:1:
simurgh.cpp: In function 'int get_cnt(std::vector<int>)':
simurgh.cpp:94:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |  assert(r.size() == n-1);
      |         ~~~~~~~~~^~~~~~
simurgh.cpp: In function 'void bs(std::vector<int>, int)':
simurgh.cpp:107:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |  for (int i = 0;i < part.size();++i)
      |                 ~~^~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:142:7: warning: unused variable 'cnt' [-Wunused-variable]
  142 |   int cnt = 0;
      |       ^~~
simurgh.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
simurgh.cpp:209:3: note: in expansion of macro 'DE'
  209 |   DE(i, j, state[i][j]);
      |   ^~

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