Submission #409010

#	Time	Username	Problem	Language	Result	Execution time	Memory
409010		ja_kingy	Simurgh (IOI17_simurgh)	C++14	100 / 100	1427 ms	7640 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
int n, seen[500], usede[125000], in_set[500], royal[125000], cnt;
vector<pii> adj[500];
vector<int> u,v;

struct DSU {
	vector<int> dsu;
	DSU (int n) {
		dsu.resize(n);
		iota(dsu.begin(), dsu.end(), 0);
	}
	int f(int x) {return dsu[x] == x ? x : dsu[x] = f(dsu[x]);}
	bool merge(int a, int b) {
		a = f(a), b = f(b);
		if (a != b) {
			dsu[b] = a;
			return 1;
		}
		return 0;
	}
};

void dfs(int u, int ma, int ex, vector<int> &r, DSU &dsu) {
	seen[u] = cnt;
	for (pii v: adj[u]) {
		if (u == ma && dsu.f(v.first) == ex) continue;
		if (dsu.f(u) == ex && v.first == ma) continue;
		if (seen[v.first] != cnt) {
			r.push_back(v.second);
			dfs(v.first, ma, ex, r, dsu);
		}
	}
}

void dfs2(int u, vector<int> &r) {
	seen[u] = cnt;
	for (pii v: adj[u]) {
		if (seen[v.first] != cnt) {
			if (!in_set[v.first]) r.push_back(v.second);
			dfs2(v.first, r);
		}
	}
}

int query(int offset, vector<int> &edges, vector<int> &span) {
	vector<int> res = edges;
	DSU dsu(n);
	for (int e: edges) {
		dsu.merge(u[e], v[e]);
	}
	for (int e: span) {
		if (dsu.merge(u[e], v[e])) {
			res.push_back(e);
			offset += royal[e];
		}
	}
	return count_common_roads(res) - offset;
}

void dnc(int cnt, int offset, vector<int> &edges, vector<int> &span) {
	if (cnt == 0) return;
	if (cnt == edges.size()) {
		for (int e: edges) royal[e] = 1;
		return;
	}
	int m = edges.size() / 2;
	vector<int> lft, rht;
	for (int e: edges) {
		(lft.size() < m ? lft : rht).push_back(e);
	}
	int res = query(offset, lft, span);
	dnc(res, offset, lft, span);
	dnc(cnt-res, offset, rht, span);	
}

std::vector<int> find_roads(int _n, std::vector<int> _u, std::vector<int> _v) {
	n = _n;
	u = _u;
	v = _v;
	vector<int> ans, stk{0}, span;
	in_set[0] = 1;
	for (int i = 0; i < u.size(); ++i) {
		adj[u[i]].push_back({v[i], i});
		adj[v[i]].push_back({u[i], i});
	}
	while (stk.size()) {
		int i = stk.back(); stk.pop_back();
		vector<int> nxt;
		DSU dsu(n);
		for (int j = 0; j < u.size(); ++j) {
			if (u[j] != i && v[j] != i)	dsu.merge(u[j], v[j]);
		}
		vector<vector<pii>> es(n);
		for (pii e: adj[i]) es[dsu.f(e.first)].push_back(e);
		vector<int> vals = dsu.dsu;
		sort(vals.begin(), vals.end());
		vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
		for (int ex: vals) if (ex != i) {
			vector<int> r;
			cnt++;
			for (int j = 0; j < n; ++j) if (j != i && seen[j] != cnt) {
				dfs(j, i, ex, r, dsu);
			}
			bool seen_royal = 0;
			vector<pii> res;
			for (pii e: es[ex]) {
				if (!usede[e.second] || (!seen_royal && royal[e.second])) {
					if (!in_set[e.first]) {
						in_set[e.first] = 1;
						nxt.push_back(e.first);
						span.push_back(e.second);
					}
					usede[e.second] = 1;
					if (royal[e.second]) seen_royal = 1;
					r.push_back(e.second);
					res.push_back({count_common_roads(r), e.second});
					r.pop_back();
				}
			}
			sort(res.begin(), res.end());
			int bst = res.back().first;
			while (res.size() && res.back().first == bst) {
				if (!royal[res.back().second]) {
					royal[res.back().second] = 1;
				}
				res.pop_back();
			}
		}
		vector<int> total_span = span;
		cnt++;
		dfs2(0, total_span);
		int span_rcnt = 0;
		for (int e: span) span_rcnt += royal[e];
		for (int nx: nxt) {
			vector<int> edges;
			stk.push_back(nx);
			for (pii e: adj[nx]) if (in_set[e.first] && !usede[e.second]) {
				edges.push_back(e.second);
				usede[e.second] = 1;
			}
			int offset = count_common_roads(total_span) - span_rcnt;
			dnc(query(offset, edges, total_span), offset, edges, total_span);
		}
	}
	for (int i = 0; i < u.size(); ++i) if (royal[i]) ans.push_back(i);
	return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'void dnc(int, int, std::vector<int>&, std::vector<int>&)':
simurgh.cpp:66:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  if (cnt == edges.size()) {
      |      ~~~~^~~~~~~~~~~~~~~
simurgh.cpp:73:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |   (lft.size() < m ? lft : rht).push_back(e);
      |    ~~~~~~~~~~~^~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  for (int i = 0; i < u.size(); ++i) {
      |                  ~~^~~~~~~~~~
simurgh.cpp:94:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   for (int j = 0; j < u.size(); ++j) {
      |                   ~~^~~~~~~~~~
simurgh.cpp:149:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |  for (int i = 0; i < u.size(); ++i) if (royal[i]) ans.push_back(i);
      |                  ~~^~~~~~~~~~

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