Submission #782458

#	Time	Username	Problem	Language	Result	Execution time	Memory
782458		GusterGoose27	Simurgh (IOI17_simurgh)	C++17	30 / 100	92 ms	4644 KiB

simurgh

#include "simurgh.h"

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;

const int MAXN = 501;
vector<pii> edges[MAXN];
set<int> ans;
int n, m;
int uf[MAXN];
int sz[MAXN];
int vis[MAXN];

int find(int i) {
	return uf[i] == i ? i : uf[i] = find(uf[i]);
}

void dfs(int s, int col) {
	vis[s] = col;
	for (pii p: edges[s]) {
		if (vis[p.first]) continue;
		dfs(p.first, col);
	}
}

vector<int> queries;
vector<int> u, v;
vector<int> undo;

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	assert(a != b);
	if (sz[a] < sz[b]) swap(a, b);
	uf[b] = a;
	sz[a] += sz[b];
	undo.push_back(b);
}

void rollback() {
	int v = undo.back(); undo.pop_back();
	sz[uf[v]] -= sz[v];
	uf[v] = v;
}

void make_mst(int cur, int col) {
	int num = 0;
	for (int i = 0; i < m; i++) {
		int a = u[i], b = v[i];
		if (find(a) == find(b) || vis[b] == col && a == cur || vis[a] == col && b == cur) continue;
		merge(a, b);
		num++;
		queries.push_back(i);
	}
	for (int i = 0; i < num; i++) rollback();
}

void get(vector<pii> &group, int col, int cur) {
	queries.clear();
	make_mst(cur, col);
	vector<int> vals;
	int mx = 0;
	bool one_big = 0;
	for (pii p: group) {
		if (ans.find(p.second) != ans.end()) {
			if (one_big) {
				vals.push_back(0);
				continue;
			}
			one_big = 1;
		}
		queries.push_back(p.second);
		vals.push_back(count_common_roads(queries));
		mx = max(mx, vals.back());
		queries.pop_back();
	}
	for (int i = 0; i < group.size(); i++) {
		if (vals[i] == mx) ans.insert(group[i].second);
	}
	// if (group.size() == 1) {
	// 	ans.insert(group[0].second);
	// 	return 1;
	// }
	// vector<pii> left, right;
	// for (int i = 0; i < group.size()/2; i += 2) {
	// 	merge(group[i].first, group[i+1].first);
	// 	left.push_back(group[i]);
	// 	right.push_back(group[i+1]);
	// }
	// if (group.size() & 1) {
	// 	left.push_back(group.back());
	// 	right.push_back(group.back());
	// }
	// queries.clear();
	// make_mst(cur, col); // ignore stuff from current to subtree
	// for (pii p: left) queries.push_back(p.second);
	// int va = count_common_roads(queries);
	// for (pii p: left) queries.pop_back();
	// for (pii p: right) queries.push_back(p.second);
	// int vb = count_common_roads(queries);
	// if (va < vb) {
	// 	swap(va, vb);
	// 	swap(left, right);
	// }
	// assert(va >= vb);
	// int num = get(left, col, cur);
	// if (!(group.size() & 1)) {
	// 	assert(va-num <= vb);
	// 	if (va-num < vb) return num+get(right, col, cur);
	// 	return num;
	// }
	// else {
	// 	bool ex = (ans.find(group.back().second) != ans.end());
	// 	num -= ex;
	// 	merge(group[0].first, group.back().first);
	// 	right.pop_back();
	// 	assert(va-num <= vb);
	// 	if (va-num < vb) return num+ex+get(right, col, cur);
	// 	return num+ex;
	// }
	// assert(false);
}

void solve(int i) {
	fill(vis, vis+n, 0);
	int t = 0;
	vis[i] = 1;
	for (pii e: edges[i]) {
		if (vis[e.first]) continue;
		dfs(e.first, ++t);
	}
	vector<vector<pii>> groups(t);
	for (pii e: edges[i]) {
		groups[vis[e.first]-1].push_back(e);
	}
	for (int j = 0; j < groups.size(); j++) {
		iota(uf, uf+n, 0);
		fill(sz, sz+n, 1);
		get(groups[j], j+1, i);
	}
}

vector<int> find_roads(int N, vector<int> U, vector<int> V) {
	n = N;
	m = U.size();
	for (int i = 0; i < m; i++) {
		u.push_back(U[i]);
		v.push_back(V[i]);
	}
	for (int i = 0; i < m; i++) {
		edges[u[i]].push_back(pii(v[i], i));
		edges[v[i]].push_back(pii(u[i], i));
	}
	for (int i = 0; i < n; i++) solve(i);
	vector<int> res;
	for (int v: ans) res.push_back(v);
	return res;
}

Compilation message (stderr)

simurgh.cpp: In function 'void make_mst(int, int)':
simurgh.cpp:52:43: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   52 |   if (find(a) == find(b) || vis[b] == col && a == cur || vis[a] == col && b == cur) continue;
      |                             ~~~~~~~~~~~~~~^~~~~~~~~~~
simurgh.cpp:52:72: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   52 |   if (find(a) == find(b) || vis[b] == col && a == cur || vis[a] == col && b == cur) continue;
      |                                                          ~~~~~~~~~~~~~~^~~~~~~~~~~
simurgh.cpp: In function 'void get(std::vector<std::pair<int, int> >&, int, int)':
simurgh.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for (int i = 0; i < group.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~
simurgh.cpp: In function 'void solve(int)':
simurgh.cpp:138:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |  for (int j = 0; j < groups.size(); j++) {
      |                  ~~^~~~~~~~~~~~~~~

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