oj.uz

Submission #423158

# Submission time Handle Problem Language Result Execution time Memory
423158 2021-06-10T19:16:28 Z Pbezz Simurgh (IOI17_simurgh) C++14
0 / 100
 3000 ms 292 KB 
#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
typedef pair<ll,ll> pii;

const ll MAXN=2e5+5;
const ll INF=1e9+7;

bitset<10>visited;
vector<vector<ll>>adj(10);
bool ok=true;

void dfs(ll node, ll p){ if(ok==false)return;
visited[node]=1;

for(auto next:adj[node]){if(ok==false)return;
if(next==p)continue;

if(visited[next]==1){
ok=false; return;
}

dfs(next,node);

}

}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	std::vector<int> r(n - 1);

	ll m=(ll)u.size(),i,k;

	for(i=0;i<(1LL<<m);i++){

	if(__builtin_popcountll(i)!=n-1)continue;

//	cout<<i<<endl;

	visited.reset();

	for(k=0;k<n;k++)adj[k].resize(0);

	for(k=0;k<m;k++){
	if(i&(1LL<k)){
	adj[u[k]].pb(v[k]);
	adj[v[k]].pb(u[k]);
	
	}
}
	ok=true;
	dfs(0,-1);

	if(ok==false)continue;

	if((ll)visited.count()==n){
	r.resize(0);

	for(k=0;k<m;k++){
	if(i&(1LL<k)){
	r.pb(k);
	}
	}

	if(count_common_roads(r)==n)return r;

}

}




	return r;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 292 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 292 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 292 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 292 KB WA in grader: NO
2 Halted 0 ms 0 KB -