Submission #248854

#	Time	Username	Problem	Language	Result	Execution time	Memory
248854		kostia244	Simurgh (IOI17_simurgh)	C++17	51 / 100	216 ms	4608 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;
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;
}
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});
	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;
		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);
	}
	
	std::vector<int> r;
	//for(int i = 0; i < m; i++) cout << state[i] << " "; cout << '\n';
	for(int i = 0; i < m; i++) if(state[i] != 1) 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:45: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:46: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:91:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < t.size(); i++)
                  ~~^~~~~~~~~~

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