Submission #1052822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052822		pcc	Simurgh (IOI17_simurgh)	C++17	100 / 100	145 ms	9176 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;
int N;
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);
	}
	void init(){
		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;
			for(auto &i:v)tp[i] = 0;
		}
		else if(normal>mn){
			tp[eid] = 0;
			for(auto &i:v)tp[i] = 1;
		}
	}
	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;
		}
	}
	return;
}

void solve(int eid){
	auto [a,b] = edges[eid];
	if(dep[a]>dep[b])swap(a,b);
	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;
	bool done = true;
	for(auto &i:v){
		if(tp[i] == -1)done = false;
		if(tp[i] != -1)checker = i;
	}
	if(done)return;
	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];
				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;
				st.insert(i);
				st.erase(eid);
			}
		}
	}
	//cerr<<"EDGES: ";for(int i = 0;i<edges.size();i++)cerr<<tp[i]<<' ';cerr<<endl;
	return;
}

int get_num(vector<int> &tar){
	dsu.init();
	vector<int> v;
	for(auto &i:tar){
		auto [a,b] = edges[i];
		if(dsu.root(a) == dsu.root(b)){
			cerr<<"WA: not forest!"<<endl;
			assert(false);
		}
		dsu.onion(a,b);
		v.push_back(i);
	}
	int s = 0;
	for(auto &i:tree_edge){
		if(tp[i] == -1){
			cerr<<"WA tree not known!"<<endl;
			assert(false);
		}
		auto [a,b] = edges[i];
		if(dsu.root(a) == dsu.root(b))continue;
		dsu.onion(a,b);
		v.push_back(i);
		s += tp[i];
	}
	if(v.size() != N-1){
		cerr<<"WA: not asking a tree!"<<endl;
		cerr<<v.size()<<endl;
		assert(false);
	}
	int re = ask(v);
	return re-s;
}

void dc(vector<int> edges,int cnt){
	if(!cnt||edges.empty())return;
	if(cnt == edges.size()){
		for(auto &i:edges){
			tp[i] = 1;
		}
		return;
	}
	vector<int> lv,rv;
	int mid = edges.size()>>1;
	for(int i = 0;i<edges.size();i++){
		if(i<mid)lv.push_back(edges[i]);
		else rv.push_back(edges[i]);
	}
	int lc = get_num(lv),rc = cnt-lc;
	dc(lv,lc);dc(rv,rc);
}

void calc(int now){
	vector<int> edges;
	for(auto [_,id]:paths[now]){
		if(tp[id] == -1)edges.push_back(id);
	}
	dc(edges,get_num(edges));
	for(auto &i:edges){
		if(tp[i] == -1)tp[i] = 0;
	}
	return;
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	N = n;
	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);
	for(auto &i:tree_edge){
		if(tp[i] == -1)tp[i] = 1;
	}
	for(int i = 0;i<N;i++){
		calc(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:118:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |   for(int i = 0;i<v.size();i++){
      |                 ~^~~~~~~~~
simurgh.cpp: In function 'void solve(int)':
simurgh.cpp:157:10: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  157 |     auto [a,b] = edges[i];
      |          ^~~~~
simurgh.cpp: In function 'int get_num(std::vector<int>&)':
simurgh.cpp:196:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  196 |  if(v.size() != N-1){
      |     ~~~~~~~~~^~~~~~
simurgh.cpp: In function 'void dc(std::vector<int>, int)':
simurgh.cpp:207:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  207 |  if(cnt == edges.size()){
      |     ~~~~^~~~~~~~~~~~~~~
simurgh.cpp:215:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  215 |  for(int i = 0;i<edges.size();i++){
      |                ~^~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:239:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  239 |  for(int i = 0;i<u.size();i++){
      |                ~^~~~~~~~~
simurgh.cpp:261: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]
  261 |  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: 19 / 19
• Subtask 5: 30 / 30