Submission #1048523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048523		pcc	Simurgh (IOI17_simurgh)	C++17	51 / 100	197 ms	7484 KiB

simurgh

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

#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 550;
pii par[mxn];
vector<pii> paths[mxn];
vector<pii> tree[mxn];
vector<int> back_edge;
int tp[mxn*mxn];
vector<pii> edges;
int dep[mxn];
vector<int> tree_edge;
set<int> tree_st;
int normal = 0;

/*
std::vector<int> r(n - 1);
for(int i = 0; i < n - 1; i++)
	r[i] = i;
int common = count_common_roads(r);
if(common == n - 1)
	return r;
r[0] = n - 1;
return r;
*/

struct DSU{
	int dsu[mxn],sz[mxn];
	DSU(){
		iota(dsu,dsu+mxn,0);
		fill(sz,sz+mxn,1);
	}
	int root(int k){
		return k == dsu[k]?k:dsu[k] = root(dsu[k]);
	}
	void onion(int a,int b){
		a = root(a),b = root(b);
		if(a == b)return;
		if(sz[a]<sz[b])swap(a,b);
		sz[a] += sz[b];
		dsu[b] = a;
	}
};
DSU dsu;

void dfs(int now,int fa){
	for(auto &[nxt,id]:paths[now]){
		if(nxt == fa)continue;
		if(par[nxt].fs == -1){
			tree_edge.push_back(id);
			par[nxt] = pii(now,id);
			dep[nxt] = dep[now]+1;
			dfs(nxt,now);
		}
		else{
			back_edge.push_back(id);
		}
	}
	return;
}

int C = 0;

int ask(vector<int> &v){
	C++;
	assert(C<=30000);
	int re = count_common_roads(v);
	return re;
}

int ask(set<int> &st){
	vector<int> v;
	for(auto &i:st)v.push_back(i);
	return ask(v);
}

void solve_cycle(vector<int> &v,int eid){
	vector<int> res;
	auto st = tree_st;
	st.insert(eid);
	for(auto &i:v){
		st.erase(i);
		res.push_back(ask(st));
		st.insert(i);
	}
	st.erase(eid);
	int mn = *min_element(res.begin(),res.end());
	int mx = *max_element(res.begin(),res.end());
	//cerr<<"CYCLE: "<<mx<<' '<<mn<<endl;for(auto &i:v)cerr<<i<<',';cerr<<endl;for(auto &i:res)cerr<<i<<',';cerr<<endl;
	if(mn == mx){
		if(normal == mn){
			tp[eid] = 0;
			for(auto &i:v)tp[i] = 0;
		}
		else if(normal<mn){
			tp[eid] = 1;dsu.onion(edges[eid].fs,edges[eid].sc);
			for(auto &i:v)tp[i] = 0;
		}
		else if(normal>mn){
			tp[eid] = 0;
			for(auto &i:v)tp[i] = 1,dsu.onion(edges[i].fs,edges[i].sc);
		}
	}
	else{
		assert(mx-mn == 1);
		if(mx>normal)tp[eid] = 1;
		else tp[eid] = 0;
		for(int i = 0;i<v.size();i++){
			if(res[i] == mx)tp[v[i]] = 0;
			else tp[v[i]] = 1,dsu.onion(edges[v[i]].fs,edges[v[i]].sc);
		}
	}
	return;
}

void solve(int eid){
	auto [a,b] = edges[eid];
	if(dep[a]>dep[b])swap(a,b);
	if(dsu.root(a) == dsu.root(b)){
		tp[eid] = 0;
		return;
	}
	int tmp = b;
	vector<int> v;
	while(tmp != a){
		v.push_back(par[tmp].sc);
		tmp = par[tmp].fs;
		//cerr<<v.back()<<','<<tmp<<' '<<a<<endl;
	}
	//cerr<<"SOLVE: "<<eid<<"::";for(auto &i:v)cerr<<i<<',';cerr<<endl;
	int checker = -1;
	for(auto &i:v){
		if(tp[i] != -1)checker = i;
	}
	if(checker == -1)solve_cycle(v,eid);
	else{
		auto st = tree_st;
		st.erase(checker);
		st.insert(eid);
		int re = ask(st);
		if(re == normal)tp[eid] = tp[checker];
		else tp[eid] = tp[checker]^1;
		st.erase(eid);
		st.insert(checker);
		//cerr<<"CHECKER: "<<checker<<','<<re<<endl;
		for(auto &i:v){
			if(tp[i] == -1){
				auto [a,b] = edges[i];
				if(dsu.root(a) == dsu.root(b)){
					continue;
				}
				st.erase(i);
				st.insert(eid);
				//cerr<<i<<"::";for(auto &j:st)cerr<<j<<',';cerr<<ask(st)<<endl;
				if(ask(st) == normal)tp[i] = tp[eid];
				else tp[i] = tp[eid]^1;
				if(tp[i]){
					dsu.onion(a,b);
				}
				st.insert(i);
				st.erase(eid);
			}
		}
	}
	//cerr<<"EDGES: ";for(int i = 0;i<edges.size();i++)cerr<<tp[i]<<' ';cerr<<endl;
	return;
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	memset(tp,-1,sizeof(tp));
	for(auto &i:par)i = pii(-1,-1);
	for(int i = 0;i<u.size();i++){
		int a = u[i],b = v[i];
		edges.push_back(pii(a,b));
		paths[a].push_back(pii(b,i));
		paths[b].push_back(pii(a,i));
	}
	par[0] = pii(0,-1);
	dfs(0,0);
	sort(back_edge.begin(),back_edge.end());
	back_edge.resize(unique(back_edge.begin(),back_edge.end())-back_edge.begin());
	for(auto &i:tree_edge)tree_st.insert(i);
	//cerr<<"TREE :";for(auto &i:tree_edge)cerr<<i<<',';cerr<<endl;
	normal = ask(tree_edge);
	//cerr<<"NORMAL: "<<normal<<endl;
	for(auto &i:back_edge)solve(i);
	vector<int> ans;
	for(int i = 0;i<edges.size();i++)if(tp[i] != 0)ans.push_back(i);
	//cerr<<C<<" ASKS"<<endl;
	//cerr<<"ANS: ";for(auto &i:ans)cerr<<i<<',';cerr<<endl;
	return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'void solve_cycle(std::vector<int>&, int)':
simurgh.cpp:113:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for(int i = 0;i<v.size();i++){
      |                 ~^~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:177:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |  for(int i = 0;i<u.size();i++){
      |                ~^~~~~~~~~
simurgh.cpp:193:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |  for(int i = 0;i<edges.size();i++)if(tp[i] != 0)ans.push_back(i);
      |                ~^~~~~~~~~~~~~

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