#include<bits/stdc++.h>
#define pb push_back
using namespace std;
#define for2(a,b,c) for(int a = b; a < c; a++)
#include "simurgh.h"
const int maxn = 510;
int adj[maxn][maxn];
bool seen[maxn];
bool burn[maxn];
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
std::vector<int> res(n - 1);
int m = u.size();
srand(10);
vector<int> sh(n);
for2(i,0,n) sh[i] = i;
random_shuffle(sh.begin(),sh.end());
for2(i,0,m){
/////////////
continue;
///////////////
u[i] = sh[u[i]];
v[i] = sh[v[i]];
}
for2(i,0,m) adj[u[i]][v[i]] = adj[v[i]][u[i]] = i;
vector<int> tree;
tree.pb(0);
seen[0] = 1;
int rep = 0;
while(tree.size() != n){
// cout << rep << endl;
// for(auto x : res) cout <<x << ' ';
// cout << endl;
for(auto x : tree)if(!burn[x]){
burn[x] = 1;
int cnt = rep;
for2(i,0,n)if(!seen[i]) res[cnt++] = adj[i][x];
int get = (count_common_roads(res));
if(rep == get) continue;
// cout << x << endl;
int last = -1;
cnt = rep;
for2(i,0,n) if(!seen[i]){
if(last != -1){
res[cnt++] = adj[i][last];
}
last = i;
}
// for(auto x : res) cout << x << ' ';
// cout << endl;
vector<int> c;
int mx = 0;
for2(i,0,n)if(!seen[i]){
res[cnt] = adj[i][x];
c.pb(count_common_roads(res));
// cout << c.back() << endl;
mx = max(mx,c.back());
}
// cout << mx << endl;
cnt = 0;
for2(i,0,n) if(!seen[i]){
if(c[cnt++] == mx){
tree.pb(i);
seen[i] = 1;
res[rep] = adj[i][x];
rep++;
}
}
}
}
return res;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(tree.size() != n){
~~~~~~~~~~~~^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
correct |
2 |
Correct |
2 ms |
452 KB |
correct |
3 |
Correct |
3 ms |
452 KB |
correct |
4 |
Incorrect |
2 ms |
460 KB |
WA in grader: NO |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
correct |
2 |
Correct |
2 ms |
452 KB |
correct |
3 |
Correct |
3 ms |
452 KB |
correct |
4 |
Incorrect |
2 ms |
460 KB |
WA in grader: NO |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
correct |
2 |
Correct |
2 ms |
452 KB |
correct |
3 |
Correct |
3 ms |
452 KB |
correct |
4 |
Incorrect |
2 ms |
460 KB |
WA in grader: NO |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
520 KB |
correct |
2 |
Correct |
3 ms |
536 KB |
correct |
3 |
Incorrect |
39 ms |
2640 KB |
WA in grader: NO |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
correct |
2 |
Correct |
2 ms |
452 KB |
correct |
3 |
Correct |
3 ms |
452 KB |
correct |
4 |
Incorrect |
2 ms |
460 KB |
WA in grader: NO |
5 |
Halted |
0 ms |
0 KB |
- |