Submission #243433

#	Time	Username	Problem	Language	Result	Execution time	Memory
243433		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>
#include "simurgh.h"
//#define local
using namespace std;
int n,m;
vi u,v,adj[505];
bool good[25500],vis[505]; // if good[i] = 1, edge[u[i]v[i] ]  =  good
int type[25500];
map<pii,int> id;
set<int> query;


int tin[505],tout[505],timer,w[505],P[505],num,wow[25005];
#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;
	set <int> good,bad;
	sort(parents.begin(),parents.end(),[&](int i,int j) {
		return tin[i] > tin[j];
	});
//	cout << v <<'\t';
	//for (int i : parents) cout << i <<' ';
	cout << endl;
	for (int i = 1; i < parents.size();i++) {
		int cnt = num;
		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();
			int id2 = id[{curnode,P[curnode]}];
			if (cnt < num) {
				good.insert(id1);
				bad.insert(id2);
			}
			else if (cnt > num) {
				bad.insert(id1);
				good.insert(id2);
			}
			else {
				same.pb({id1,id2});
			}
			if (P[curnode] != parents[i])
			insert(curnode,P[curnode]);
			else erased.pb(id[{curnode,parents[i]}]);
			curnode = P[curnode];
		}while(curnode != parents[i]);
		//query.erase(id[{parents[i-1],v}]);
		//query.insert(id[{parents[i],v}]);
		//num = ask();
		//if (num)
	} 
	for (int i : erased) query.insert(i);
//	for(int i = 1 ; i < parents.size();i++)
while(parents.size() >= 2) {
erase(v,parents.back());
parents.pop_back();
}
	vi seen(505);
	vector<vi> e(505);
	for (auto i : same) {
		e[i.fi].pb(i.se);
		e[i.se].pb(i.fi);
	}
	for (int i : good) {
		queue<int> q;
		type[i] = 1;
		seen[i] = 1;
		q.push(i);
		while(!q.empty()) {
			int v = q.front();
			q.pop();
			for (int j : e[i]) {
				if (seen[j]) continue;
				seen[j] = 1;
				q.push(j);
			}
		}
	}
	for (int i : bad) {
		queue<int> q;
		type[i] = -1;
		seen[i] = 1;
		q.push(i);
		while(!q.empty()) {
			int v = q.front();
			q.pop();
			for (int j : e[i]) {
				if (seen[j]) continue;
				seen[j] = 1;
				q.push(j);
			}
		}
	}
	P[v] = p;
	if (good.empty() && bad.empty() && w[v] <= tin[v]) {
	for (int i : parents) type[id[{v,i}]] = 1;
	if (parents.size()){
		int t = 10;
	for (int i = v; i != parents.back() && t ; t--,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();
	
	memset(vis,0,sizeof vis);
	vector<int> g = {-1};
//	return g;
	dfs(0,-1);
	
//	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:82:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < parents.size();i++) {
                  ~~^~~~~~~~~~~~~~~~
simurgh.cpp:134:8: warning: unused variable 'v' [-Wunused-variable]
    int v = q.front();
        ^
simurgh.cpp:149:8: warning: unused variable 'v' [-Wunused-variable]
    int v = q.front();
        ^

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