Submission #259101

#	Time	Username	Problem	Language	Result	Execution time	Memory
259101		dsjong	Simurgh (IOI17_simurgh)	C++14	30 / 100	3083 ms	20256 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
set<int>adj[505];
map<pair<int, int>, int>mp;
int roads;
bool vis[505];
int a[200000], val[200000], par[505], l[505];
int timer=0;
pair<int, int>cur={-1, -1};
void dfs(int x, int p){
	vis[x]=true;
	par[x]=p;
	l[x]=timer++;
	for(int y:adj[x]){
		if(!vis[y]) dfs(y, x);
		else if(y!=p && l[y]<=l[x]){
			cur={x, y};
		}
	}
}
vector<int>test, query, oq;
void bfs(){
	memset(vis, false, sizeof vis);
	queue<int>q;
	for(int i=0;i<test.size()-1;i++){
		vis[test[i]]=true;
		q.push(test[i]);
	}
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int y:adj[x]){
			if(!vis[y]){
				q.push(y);
				vis[y]=true;
				query.push_back(mp[{x, y}]-1);
			}
		}
	}
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	int m=u.size();
	roads=m;
	for(int i=0;i<m;i++){
		adj[u[i]].insert(v[i]);
		adj[v[i]].insert(u[i]);
		mp[{u[i], v[i]}]=i+1;
		mp[{v[i], u[i]}]=i+1;
	}
	while(roads>=n){
		//cout<<roads<<endl;
		memset(vis, false, sizeof vis);
		dfs(0, -1);
		int x=cur.first, y=cur.second, ox=cur.first;
		test.clear();
		while(x!=y){
			test.push_back(x);
			x=par[x];
		}
		test.push_back(y);
		test.push_back(ox);
		/*for(int i:test) cout<<i<<" ";
			cout<<endl;*/
		query.clear();
		bfs();
		int mini=0, sz=test.size();
		for(int i=0;i<sz-1;i++){
			oq=query;
			if(a[mp[{test[i], test[i+1]}]]!=0) continue;
			for(int j=0;j<sz-1;j++){
				if(j!=i) query.push_back(mp[{test[j], test[j+1]}]-1);
			}
			/*cout<<"querying ";
			for(int i:query) cout<<i<<" ";
				cout<<endl;*/
			val[i]=count_common_roads(query);
			mini=max(mini, val[i]);
			query=oq;
		}
		for(int i=0;i<sz-1;i++){
			if(a[mp[{test[i], test[i+1]}]]!=0) continue;
			if(val[i]==mini){
				//cout<<"delet "<<test[i]<<" "<<test[i+1]<<": "<<mp[{test[i], test[i+1]}]-1<<endl;
				a[mp[{test[i], test[i+1]}]]=1;
				adj[test[i]].erase(test[i+1]);
				adj[test[i+1]].erase(test[i]);
				roads--;
			}
			else{
				//cout<<"fix "<<test[i]<<" "<<test[i+1]<<": "<<mp[{test[i], test[i+1]}]-1<<endl;
				a[mp[{test[i], test[i+1]}]]=2;
			}
		}
	}
	vector<int>ans;
	for(int i=0;i<m;i++){
		if(a[i+1]!=1) ans.push_back(i);
	}
	return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'void bfs()':
simurgh.cpp:26:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<test.size()-1;i++){
              ~^~~~~~~~~~~~~~

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