oj.uz

Submission #423165

# Submission time Handle Problem Language Result Execution time Memory
423165 2021-06-10T19:28:18 Z Pbezz Simurgh (IOI17_simurgh) C++14
13 / 100
 26 ms 296 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<52>visited;
vector<vector<ll>>adj(52);
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-1)return r;

}

}




	return r;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 204 KB correct
2 Correct 16 ms 296 KB correct
3 Correct 18 ms 292 KB correct
4 Correct 1 ms 204 KB correct
5 Correct 0 ms 204 KB correct
6 Correct 2 ms 204 KB correct
7 Correct 0 ms 204 KB correct
8 Correct 0 ms 204 KB correct
9 Correct 1 ms 204 KB correct
10 Correct 1 ms 204 KB correct
11 Correct 1 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 9 ms 204 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 204 KB correct
2 Correct 16 ms 296 KB correct
3 Correct 18 ms 292 KB correct
4 Correct 1 ms 204 KB correct
5 Correct 0 ms 204 KB correct
6 Correct 2 ms 204 KB correct
7 Correct 0 ms 204 KB correct
8 Correct 0 ms 204 KB correct
9 Correct 1 ms 204 KB correct
10 Correct 1 ms 204 KB correct
11 Correct 1 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 9 ms 204 KB correct
14 Incorrect 1 ms 204 KB WA in grader: NO
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 204 KB correct
2 Correct 16 ms 296 KB correct
3 Correct 18 ms 292 KB correct
4 Correct 1 ms 204 KB correct
5 Correct 0 ms 204 KB correct
6 Correct 2 ms 204 KB correct
7 Correct 0 ms 204 KB correct
8 Correct 0 ms 204 KB correct
9 Correct 1 ms 204 KB correct
10 Correct 1 ms 204 KB correct
11 Correct 1 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 9 ms 204 KB correct
14 Incorrect 1 ms 204 KB WA in grader: NO
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB correct
2 Incorrect 26 ms 292 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 204 KB correct
2 Correct 16 ms 296 KB correct
3 Correct 18 ms 292 KB correct
4 Correct 1 ms 204 KB correct
5 Correct 0 ms 204 KB correct
6 Correct 2 ms 204 KB correct
7 Correct 0 ms 204 KB correct
8 Correct 0 ms 204 KB correct
9 Correct 1 ms 204 KB correct
10 Correct 1 ms 204 KB correct
11 Correct 1 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 9 ms 204 KB correct
14 Incorrect 1 ms 204 KB WA in grader: NO
15 Halted 0 ms 0 KB -