Submission #243473

#	Time	Username	Problem	Language	Result	Execution time	Memory
243473		crossing0ver	Simurgh (IOI17_simurgh)	C++17	0 / 100	5 ms	384 KiB

simurgh

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
//#define local
//#ifndef local
#include "simurgh.h"
//#endif

using namespace std;
int n,m;
vi u,v,adj[505],rlans;
bool good[255000],vis[505]; // if good[i] = 1, edge[u[i]v[i] ]  =  good
set<pair<int,int> > SM;
int type[255000];
map<pii,int> id;
set<int> query;
int tin[505],tout[505],timer,w[505],P[505],num,wow[250005];
/*
#ifdef local
int count_common_roads(vector<int> v) {
	int ans = 0;
	cout <<"ASK:\t";
	for (int i : v) cout << i <<' ';
	cout << endl ;
	for (int i : v) ans += wow[i];
	return ans;
}
#endif*/
//////////////
int ask() {
	vi v;
	for (int i : query) v.pb(i);
	int x = count_common_roads(v);
	return x;
}
//////////////
void erase(int a,int b) {
	query.erase(id[{a,b}]);
}
void insert(int a,int b) {
	query.insert(id[{a,b}]);
}
///////////////
void jartidfs(int v) {
	vis[v] = 1;
	for (int i : adj[v]) {
		if (!vis[i]) {
			insert(v,i);
			jartidfs(i);
		}
	}
}

void dfs(int v,int p) {
	int z = 0;
	P[v] = p;
	vi parents,erased;
	if (p != -1) parents.pb(p);
	vis[v] = 1;
	tin[v] = w[v] = z = ++timer;
	for (int i : adj[v]) {
		if (i == p) continue;
		if (vis[i]) {
			if (tin[i] < tin[v]) {
			z = min(z,tin[i]);
			parents.pb(i);
		}
		}
		else {
			dfs(i,v);
			w[v] = min(w[v],w[i]);
		}
	}
	vector<pii> dif,same;
	sort(parents.begin(),parents.end(),[&](int i,int j) {
		return tin[i] > tin[j];
	});
	int s = 0;
//	cout << v <<'\t';
	//for (int i : parents) cout << i <<' ';
	cout << endl;
	for (int i = 1; i < parents.size();i++) {
		int cnt = num = ask();
		int curnode = v;
		insert(v,parents[i]);
		P[v] = parents[i-1];
		int id1 = id[{v,parents[i]}];
		do{
			erase(curnode,P[curnode]);
		//	if(query.size()== 4){
		//		cout<<v <<'s';
		//	}
			num = ask();
		//	if (num == n-1) {
		//		rlans.clear();
		//		for (int i :query) rlans.pb(i);
		//	}
			int id2 = id[{curnode,P[curnode]}];
			if (cnt < num) {
				type[id1] = 1;
				s = 1;
				type[id2] = -1;
			}
			else if (cnt > num) {
				type[id1] = -1;
				type[id2] = 1;
				s = 1;
			}
			else {
				same.pb({id1,id2});
				SM.insert({id1,id2});
			}
			if (P[curnode] != parents[i]) {
			insert(curnode,P[curnode]);
		//	erase(v,parents[i]);
		//	cnt = ask();
		//	insert(v,parents[i]);
		}
			else erased.pb(id[{curnode,parents[i]}]);
			curnode = P[curnode];
		}while(curnode != parents[i]);
    }  
for (int i = 1; i < parents.size(); i++) {
 erase(v,parents[i]);
}
for (int i : erased) query.insert(i);
 num = ask();
	vi seen(m+1);
	map<int,vector<int> > e;
	for (auto i : same) {
		e[i.fi].pb(i.se);
		e[i.se].pb(i.fi);
	}
	for (int i = 0; i <= m; i++) {
		if (type[i] != 1) continue;
		queue<int> q;
		if (seen[i]) continue;
		seen[i] = 1;
		q.push(i);
		while(!q.empty()) {
			int v = q.front();
			type[v] = 1;
			q.pop();
			for (int j : e[i]) {
				if (seen[j]) continue;
				seen[j] = 1;
				q.push(j);
			}
		}
	}
	for (int i = 0; i <= m; i++) {
		if (type[i] != -1) continue;
		queue<int> q;
		type[i] = -1;
		if (seen[i]) continue;
		seen[i] = 1;
		q.push(i);
		while(!q.empty()) {
			int v = q.front();
			type[v] = -1;
			q.pop();
			for (int j : e[i]) {
				if (seen[j]) continue;
				seen[j] = 1;
				q.push(j);
			}
		}
	}
	P[v] = p;
	if (s == 0 && w[v] == tin[v]) {
	for (int i : parents) type[id[{v,i}]] = 1;
	if (parents.size())
	for (int i = v; i != parents.back();i = P[i]) {
		type[id[{i,P[i]}]] = 1;
	}
}
	w[v] = min(w[v],z);
}
void preprocess(int n1,vi u1, vi v1) {
	m = u1.size(); n = n1;
	u = u1; v = v1;
	for (int i = 0; i < m; i++) {
		id[{u[i],v[i]}] = id[{v[i],u[i]}] = i;
		adj[u[i]].pb(v[i]);
		adj[v[i]].pb(u[i]);
	}
}
vi find_roads(int n1, vi u1, vi v1) {
	preprocess(n1,u1,v1);
	jartidfs(0);
	num = ask();
	if (num == n-1) {
		rlans.clear();
		for (int i :query) rlans.pb(i);
	}
	
	memset(vis,0,sizeof vis);
	vector<int> g = {-1};
//	return g;
	dfs(0,-1);
	if (!rlans.empty()) return rlans;
	vi seen(m+1);
	map<int,vector<int> > e;
	for (auto i : SM) {
		e[i.fi].pb(i.se);
		e[i.se].pb(i.fi);
	}
	for (int i = 0; i <= m; i++) {
		if (type[i] != 1) continue;
		queue<int> q;
		if (seen[i]) continue;
		seen[i] = 1;
		q.push(i);
		while(!q.empty()) {
			int v = q.front();
			type[v] = 1;
			q.pop();
			for (int j : e[i]) {
				if (seen[j]) continue;
				seen[j] = 1;
				q.push(j);
			}
		}
	}
	for (int i = 0; i <= m; i++) {
		if (type[i] != -1) continue;
		queue<int> q;
		type[i] = -1;
		if (seen[i]) continue;
		seen[i] = 1;
		q.push(i);
		while(!q.empty()) {
			int v = q.front();
			type[v] = -1;
			q.pop();
			for (int j : e[i]) {
				if (seen[j]) continue;
				seen[j] = 1;
				q.push(j);
			}
		}
	}
//	vi ans(n - 1);
	//int common = count_common_roads(r);
//	if(common == n - 1)
	//	return r;
//	r[0] = n - 1;
vi ans;
for (int i = 0; i < m; i++) if (type[i] == 1) ans.pb(i);
ans.resize(n-1);
	return ans;
}/*
#ifdef local
main() {
	int n,m;	cin >> n >> m;
	vi u,v;
	for (int i = 0;i  < m ;i++ ) {
		int a, b; cin >> a >> b;
		u.pb(a);
		v.pb(b);
	}
	for (int i = 0; i < n - 1; i++) {
		int a; cin >> a;
		wow[a] = 1;
	}
	vector<int> ans = find_roads(n,u,v);
	for (int i :ans ) cout << i <<' ';
}
#endif*/

Compilation message (stderr)

simurgh.cpp: In function 'void dfs(int, int)':
simurgh.cpp:85:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < parents.size();i++) {
                  ~~^~~~~~~~~~~~~~~~
simurgh.cpp:126:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for (int i = 1; i < parents.size(); i++) {
                 ~~^~~~~~~~~~~~~~~~

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