Submission #249927

#	Time	Username	Problem	Language	Result	Execution time	Memory
249927		kostia244	Simurgh (IOI17_simurgh)	C++17	100 / 100	873 ms	7548 KiB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 505;
int n, m;
vector<array<int, 2>> g[maxn], tr[maxn];
vector<int> state, te, vis, used, U, V;
void pre(int v) {
	vis[v] = 1;
	for(auto [i, id] : g[v]) if(!vis[i]) {
		pre(i);
		used.push_back(id);
		te[id] = 1;
		tr[v].push_back({i, id});
		tr[i].push_back({v, id});
	}
}
vector<int> _path;
bool find(int v, int t) {
	if(v == t) return true;
	vis[v] = 1;
	int ok = 0;
	for(auto [i, id] : tr[v]) if(!vis[i]) {
		if(find(i, t)) _path.push_back(id), ok = 1;
	}
	return ok;
}
vector<int> find_path(int u, int v) {
	_path.clear();
	vis.assign(n, 0);
	find(u, v);
	return _path;
}
int alter(int id, int nid) {
	vector<int> t = used;
	for(auto &i : t) if(i == id) swap(i, t.back());
	t.pop_back();
	t.push_back(nid);
	int res = count_common_roads(t);
	//cout << "====query====\n";
	//for(auto i : t) cout << i << " "; cout << " :: " << res << endl;
	return res;
}

struct dsu {
	vector<int> r, p;
	dsu(int n) : r(n), p(n) {iota(p.begin(), p.end(), 0);}
	int par(int v) { return v == p[v] ? v : p[v] = par(p[v]); }
	void unite(int i, int j) {
		i = par(i), j = par(j);
		if(i == j) return;
		if(r[i] < r[j]) swap(i, j);
		p[j] = i;
		r[i] += r[j];
	}
	bool con(int i, int j) {
		return par(i) == par(j);
	}
};
int count(int v, int p) {
	vector<int> t;
	dsu d(n);
	for(int i = 0; i < p; i++) {
		t.push_back(g[v][i][1]);
		d.unite(v, g[v][i][0]);
	}
	int bias = 0;
	for(auto i : used) if(!d.con(U[i], V[i])) {
		d.unite(U[i], V[i]);
		t.push_back(i);
		bias += state[i] == 2;
	}
	bias =  count_common_roads(t) - bias;
	return bias;
}
std::vector<int> find_roads(int _n, std::vector<int> u, std::vector<int> v) {
	for(int i = 0; i < u.size(); i++) g[u[i]].push_back({v[i], i});
	for(int i = 0; i < u.size(); i++) g[v[i]].push_back({u[i], i});
	U = u, V = v;
	n = _n;
	m = u.size();
	state.resize(m);
	te.resize(m);
	vis.resize(n);
	pre(0);
	
	//cout << "Init tree is ";
	//for(auto i : used) cout << u[i] << " " << v[i] << '\n';
	int init = count_common_roads(used);
	//cout << "init " << init << endl;
	for(int i = 0; i < m; i++) if(!te[i]) {
		vector<int> t = find_path(u[i], v[i]);
		
		//cout << "Determining " << u[i] << " " << v[i] << endl;
		//cout << "Path:\n";
		//for(auto i : t) cout << u[i] << " " << v[i] << " | " << i << " " << state[i] << '\n';
		
		int det = 0, unset = 0;
		for(auto id : t) unset += state[id] == 0;
		if(unset == 0) continue;
		for(auto id : t) {
			if(state[id]) {
				int tmp = alter(id, i);
				if(state[id] == 2) det = 1+(tmp == init);
				else det = 1+(tmp>init);
				break;
			}
		}
		//cout << "det is " << det << '\n';
		if(det) {
			state[i] = det;
			for(auto &id : t) if(!state[id]) {
				int tmp = alter(id, i);
				if(det == 2) state[id] = 1+(tmp == init);
				else state[id] = 1+(tmp<init);
			}
			continue;
		}
		vector<int> results;
		int mx = init;
		for(auto id : t) {
			results.push_back(alter(id, i));
			mx = max(mx, results.back());
		}
		//cout << "Here, " << mx << '\n';
		for(int i = 0; i < t.size(); i++)
			state[t[i]] = 1+(results[i]!=mx);
		state[i] = 1+(init!=mx);
	}
	for(auto i : used) if(!state[i]) state[i] = 2;
	for(int i = 0; i < n; i++) {
		for(int j = g[i].size(); j--;) {
			if(count(used.begin(), used.end(), g[i][j][1]) || g[i][j][0] < i)
				swap(g[i][j], g[i].back()), g[i].pop_back();
		}
		int cnt = count(i, g[i].size()), p = 0;
		for(int F = 0; F < cnt; F++) {
			for(int z = 1<<9; z>>=1;)
				if(p+z <= g[i].size() && count(i, p+z) <= F) p+=z;
			state[g[i][p][1]] = 2;
		}
	}
	
	std::vector<int> r;
	//for(int i = 0; i < m; i++) cout << state[i] << " "; cout << '\n';
	//cout << "Didn't crash\n";
	for(int i = 0; i < m; i++) if(state[i] == 2) r.push_back(i);
	//for(auto i : r) cout << i << '\n';
	return r;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:77:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < u.size(); i++) g[u[i]].push_back({v[i], i});
                 ~~^~~~~~~~~~
simurgh.cpp:78:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < u.size(); i++) g[v[i]].push_back({u[i], i});
                 ~~^~~~~~~~~~
simurgh.cpp:126:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < t.size(); i++)
                  ~~^~~~~~~~~~
simurgh.cpp:139:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(p+z <= g[i].size() && count(i, p+z) <= F) p+=z;
        ~~~~^~~~~~~~~~~~~~

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