oj.uz

답안 #415100

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
415100 2021-05-31T14:23:44 Z Kevin_Zhang_TW Simurgh (IOI17_simurgh) C++17
19 / 100
 613 ms 6632 KB 
#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 qry(vector<int> r) { 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) { 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];
		assert(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;
	DE(mid, part.size(), sum, get_cnt(part));
	assert(part.size() > 0);
	for (int i = 0;i < part.size();++i)
		(i<mid?l:r).pb(part[i]);
	bs(l, get_cnt(l));
	bs(r, get_cnt(r));
}

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

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

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

		int cur_v = -1;
		if (small.size()) cur_v = 0;
		if (big.size()) cur_v = 1;
		if (cur_v == -1 && sure.size()) {
			int qv = qry( (tid - sure[0]) + id[a][b] );
			int x = v[ sure[0] ], y = u[ sure[0] ];
			if (qv > tsum) cur_v = 0;
			if (qv == tsum) cur_v = state[x][y];
			if (qv < tsum) cur_v = 1;
		}
		if (cur_v == -1 && same.size() == l.size() + r.size())
			cur_v = 0;

		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;
		DE(a, b, state[a][b]);
	}

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

Compilation message

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:92:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   92 |  assert(r.size() == n-1);
      |         ~~~~~~~~~^~~~~~
simurgh.cpp: In function 'void bs(std::vector<int>, int)':
simurgh.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
simurgh.cpp:105:2: note: in expansion of macro 'DE'
  105 |  DE(mid, part.size(), sum, get_cnt(part));
      |  ^~
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:139:7: warning: unused variable 'cnt' [-Wunused-variable]
  139 |   int cnt = 0;
      |       ^~~
simurgh.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
simurgh.cpp:195:3: note: in expansion of macro 'DE'
  195 |   DE(a, b, state[a][b]);
      |   ^~
simurgh.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
simurgh.cpp:204:3: note: in expansion of macro 'DE'
  204 |   DE(i, j, state[i][j]);
      |   ^~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 332 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 332 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 332 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 332 KB correct
3 Correct 365 ms 4844 KB correct
4 Correct 549 ms 6568 KB correct
5 Correct 549 ms 6572 KB correct
6 Correct 527 ms 6628 KB correct
7 Correct 487 ms 6584 KB correct
8 Correct 470 ms 6568 KB correct
9 Correct 613 ms 6568 KB correct
10 Correct 554 ms 6576 KB correct
11 Correct 544 ms 6572 KB correct
12 Correct 590 ms 6568 KB correct
13 Correct 1 ms 332 KB correct
14 Correct 518 ms 6632 KB correct
15 Correct 553 ms 6572 KB correct

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 332 KB WA in grader: NO
2 Halted 0 ms 0 KB -