oj.uz

Submission #259070

# Submission time Handle Problem Language Result Execution time Memory
259070 2020-08-07T06:45:38 Z dsjong Simurgh (IOI17_simurgh) C++14
0 / 100
 3000 ms 384 KB 
#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;
void dfs(int x, int p){
	vis[x]=true;
	par[x]=p;
	l[x]=timer++;
	for(int y:adj[x]){
		if(y==p) continue;
		if(!vis[y]) dfs(y, x);
		else if(l[y]<=l[x]){
			cur={x, y};
			return;
		}
	}
}
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(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){
		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=1e9, 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=min(mini, val[i]);
			query=oq;
		}
		for(int i=0;i<sz-1;i++){
			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 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

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

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3068 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3068 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3068 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB correct
2 Execution timed out 3082 ms 384 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3068 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -