#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
#define ll long long
template<typename T>
int len(T &a){
return a.size();
}
struct DSU{
vector<int> par, sz; int n;
DSU (int _n){
n = _n;
par.resize(n);
iota(all(par), 0);
sz.assign(n, 1);
}
DSU (){}
int get(int a){
return (par[a] == a ? a : par[a] = get(par[a]));
}
void init(int _n){
n = _n;
par.resize(n);
iota(all(par), 0);
sz.assign(n, 1);
}
void unite(int a, int b){
a = get(a);
b = get(b);
if(a == b) return;
if(sz[a] < sz[b]) swap(a,b);
sz[a] += sz[b];
par[b] = a;
}
void link(int a, int b){
a = get(a); b = get(b);
if(a == b) return;
sz[b] += sz[a];
par[a] = b;
}
};
int _qu = 0;
int ask(const vector<int> &gs){
_qu ++;
//assert(_qu <= 30000);
return count_common_roads(gs);
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
vector<int> royal;
int m = len(u);
DSU roy(n);
vector<int> in(m, -1);
assert(m <= 30000);
for(int i = 0; i < n - 1; i ++){
DSU t(n);
vector<int> gs;
vector<int> rem;
for(int j = 0; j < m; j ++){
if(u[j] == i || v[j] == i){
rem.push_back(j);
}else{
if(t.get(v[j]) == t.get(u[j])) continue;
gs.push_back(j);
t.unite(v[j], u[j]);
}
}
vector<vector<int>> mp;
map<int,int> id;
for(auto j : rem){
int p = t.get(u[j] ^ v[j] ^ i);
if(id.count(p) == 0){
id[p] = len(id);
mp.push_back(vector<int>());
}
mp[id[p]].push_back(j);
}
for(int j = 0; j < len(mp); j ++){
int f = -1;
if(len(mp[j]) == 1){
if(roy.get(u[mp[j][0]]) == roy.get(v[mp[j][0]])){
in[mp[j][0]] = 0;
continue;
}
royal.push_back(mp[j][0]);
roy.unite(u[mp[j][0]], v[mp[j][0]]);
in[mp[j][0]] = 1;
continue;
}else{
for(int k = 0; k < len(mp); k ++){
if(k == j){
continue;
}
gs.push_back(mp[k][0]);
}
vector<pair<int,int>> counts;
for(int k = 0; k < len(mp[j]); k ++){
if(in[mp[j][k]]) {f = mp[j][k]; break;};
}
if(f == -1){
int mx = 0;
vector<pair<int,int>> counts;
for(auto k : mp[j]){
if(in[k] == 0) continue;
gs.push_back(k);
int cnt = ask(gs);
counts.push_back({cnt, k});
gs.pop_back();
if(cnt > mx){
mx = cnt;
}
}
for(auto [cnt, k] : counts){
if(cnt == mx){
royal.push_back(k);
roy.unite(u[k], v[k]);
in[k] = 1;
}else in[k] = 0;
}
}else{
gs.push_back(f);
int mx = ask(gs);
gs.pop_back();
for(auto k : mp[j]){
if(roy.get(u[k]) == roy.get(v[k]) || in[k] == 0) continue;
gs.push_back(k);
if(ask(gs) == mx){
royal.push_back(k);
roy.unite(u[k], v[k]);
in[k] = 1;
}else in[k] = 0;
gs.pop_back();
}
}
for(int k = 0; k < len(mp) - 1; k ++){
gs.pop_back();
}
}
}
}
assert(len(royal) == n - 1);
return royal;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
correct |
| 2 |
Incorrect |
0 ms |
348 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
