제출 #706057

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
706057		Soumya1	Simurgh (IOI17_simurgh)	C++17	0 / 100	2523 ms	4236 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
#ifdef __LOCAL__
  #include <debug_local.h>
#endif
using namespace std;
const int mxN = 505;
int n, m;
int ad[mxN][mxN];
vector<int> g[mxN];
vector<pair<int, int>> edges;
struct DSU {
	int n;
	vector<int> par;
	DSU(int _n) {
		n = _n;
		par.resize(n);
		iota(par.begin(), par.end(), 0);
	}
	int find(int u) {
		return (u == par[u] ? u : find(par[u]));
	}
	bool unite(int u, int v) {
		u = find(u), v = find(v);
		if (u == v) return false;
		par[u] = v;
		return true;
	}
};
int query(vector<int> r) {
	return count_common_roads(r);
}
set<int> tree;
vector<int> nodes[mxN];
set<int> on;
int Myquery(vector<int> v) {
	vector<int> r;
	DSU dsu(n);
	for (int i : v) {
		auto [u, v] = edges[i];
		r.push_back(i);
		dsu.unite(u, v);
	}
	for (int i : on) {
		auto [u, v] = edges[i];
		if (dsu.unite(u, v)) r.push_back(i);	
	}
	for (int i : tree) {
		auto [u, v] = edges[i];
		if (dsu.unite(u, v)) r.push_back(i);
	}
	return query(r);
}
int init;
int reduction(vector<int> v) {
	vector<int> r;
	DSU dsu(n);
	for (int i : v) {
		auto [u, v] = edges[i];
		r.push_back(i);
		dsu.unite(u, v);
	}
	int ans = 0;
	for (int i : on) {
		auto [u, v] = edges[i];
		if (dsu.unite(u, v)) r.push_back(i);	
		else ans++;
	}
	for (int i : tree) {
		auto [u, v] = edges[i];
		if (dsu.unite(u, v)) r.push_back(i);
	}
	return ans;
}
void dfs(int u, int p) {
	for (int v : g[u]) {
		if (v == p) continue;
		dfs(v, u);
	}
	for (int v : g[u]) {
		if (v == p) continue;
		bool found = false, ok = true;
		// get the value of (u, v) in 3 queries
		for (int vv : g[u]) {
			if (vv == p || vv == v) continue;
			if (found) break;
			for (int a : nodes[v]) {
				if (found) break;
				for (int b : nodes[vv]) {
					if (ad[a][b] != -1) {
						int v1 = init;
						auto ntree = tree;
						ntree.erase(ad[u][vv]);
						ntree.insert(ad[a][b]);
						int v2 = query(vector<int> (ntree.begin(), ntree.end()));
						ntree.insert(ad[u][vv]);
						ntree.erase(ad[u][v]);
						int v3 = query(vector<int> (ntree.begin(), ntree.end()));
						if (v3 >= max(v1, v2)) ok = false;
						found = true;
						break;
					}
				}
			}
		}
		if (ok) on.insert(ad[u][v]);
	}
	for (int v : g[u]) {
		if (v == p) continue;
		// for each node a in subtree of v, binary search to find edges to the left subtrees
		for (int a : nodes[v]) {
			vector<int> cur;
			for (int b : nodes[u]) {
				if (ad[a][b] != -1) cur.push_back(ad[a][b]);
			}
			int L = 0;
			while (L < cur.size()) {
				int val = Myquery({});
				int lo = L, hi = cur.size();
				while (lo < hi) {
					int mid = (lo + hi) >> 1;
					int nval = Myquery(vector<int> (cur.begin() + L, cur.begin() + mid + 1));
					if (nval + reduction(vector<int> (cur.begin() + L, cur.begin() + mid + 1)) > val) {
						hi = mid;
					} else {
						lo = mid + 1;
					}
				}
				if (lo < cur.size()) {
					on.insert(cur[lo]);
				}
				L = lo + 1;
			}
		}
		for (int a : nodes[v]) {
			nodes[u].push_back(a);
		}
	}
	vector<int> cur;
	for (int b : nodes[u]) {
		if (ad[u][b] != -1) cur.push_back(ad[u][b]);
	}
	int L = 0;
	while (L < cur.size()) {
		int val = Myquery({});
		int lo = L, hi = cur.size();
		while (lo < hi) {
			int mid = (lo + hi) >> 1;
			int nval = Myquery(vector<int> (cur.begin() + L, cur.begin() + mid + 1));
			if (nval + reduction(vector<int> (cur.begin() + L, cur.begin() + mid + 1)) > val) {
				hi = mid;
			} else {
				lo = mid + 1;
			}
		}
		if (lo < cur.size()) {
			on.insert(cur[lo]);
		}
		L = lo + 1;
	}
	nodes[u].push_back(u);
}
vector<int> find_roads(int N, vector<int> U, vector<int> V) {
	memset(ad, -1, sizeof ad);
	n = N, m = U.size();
	for (int i = 0; i < m; i++) {
		ad[U[i]][V[i]] = ad[V[i]][U[i]] = i;
		edges.push_back({U[i], V[i]});
	}
	{
		DSU dsu(n);
		for (int i = 0; i < m; i++) {
			auto [u, v] = edges[i];
			if (dsu.unite(u, v)) {
				tree.insert(i);
				g[u].push_back(v);
				g[v].push_back(u);
			}
		}
	}
	init = query(vector<int> (tree.begin(), tree.end()));
	dfs(0, -1);
	// debug(on);
	return vector<int> (on.begin(), on.end());
}

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

simurgh.cpp: In function 'void dfs(int, int)':
simurgh.cpp:117:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |    while (L < cur.size()) {
      |           ~~^~~~~~~~~~~~
simurgh.cpp:129:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     if (lo < cur.size()) {
      |         ~~~^~~~~~~~~~~~
simurgh.cpp:144:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |  while (L < cur.size()) {
      |         ~~^~~~~~~~~~~~
simurgh.cpp:156:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |   if (lo < cur.size()) {
      |       ~~~^~~~~~~~~~~~

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