#include<bits/stdc++.h>
#include "simurgh.h"
using namespace std;
const int N = 510;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
struct DSU {
vector<int> p;
vector<vector<int>> st;
void init(int n) {
p.resize(n), st.resize(n);
for(int i = 0; i < n; i++) {
p[i] = i;
st[i].push_back(i);
}
}
int find(int x) {
return p[x] = (p[x] == x ? x : find(p[x]));
}
void merge(int u, int v) {
u = find(u);
v = find(v);
if(u == v) return;
if((int)st[u].size() < (int)st[v].size())
swap(u, v);
p[v] = u;
for(auto c : st[v])
st[u].push_back(c);
}
};
struct edge {
int u, v, inx;
int to(int u) {
return (this->u == u ? this->v : this->u);
}
};
DSU ds;
vector<int> g[N];
edge e[N * N];
int type[N * N], royal_cnt = 0;
// 0 = unknown, 1 = royal, 2 = common
void coloring(int x, int cl) {
x = ds.find(x);
for(int c : ds.st[x]) {
type[c] = cl;
royal_cnt += (cl == 1);
}
}
int n, m;
int tin[N], tout[N], T = 0;
vector<bool> vis;
vector<int> used;
void dfs(int s = 0) {
vis[s] = 1;
tin[s] = T++;
for(int i : g[s]) {
if(!vis[e[i].to(s)] && !type[i]) {
used.push_back(i);
dfs(e[i].to(s));
}
}
for(int i : g[s]) {
if(!vis[e[i].to(s)] && type[i] == 1) {
used.push_back(i);
dfs(e[i].to(s));
}
}
tout[s] = T++;
}
bool up(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
vector<int> travel() {
vis.assign(n, false);
used.clear();
T = 0;
dfs();
return used;
}
bool isAble(int i, int j) {
int u = e[i].u, v = e[i].v;
int x = e[i].u, y = e[i].v;
if(tin[u] > tin[v]) swap(u, v);
if(tin[x] > tin[y]) swap(x, y);
return (up(v, y) && up(x, u));
}
vector<int> find_roads(int N, vector<int> u, vector<int> v) {
n = N;
m = (int)u.size();
for(int i = 0; i < m; i++) {
e[i] = {u[i], v[i], i};
g[u[i]].push_back(i);
g[v[i]].push_back(i);
}
ds.init(m);
while(royal_cnt < n - 1) {
vector<int> w = travel();
int res0 = count_common_roads(w);
if(res0 == n - 1) return w;
vector<int> un_w;
for(int inx : w) {
if(!type[inx])
un_w.push_back(inx);
}
int chosen = un_w[rnd() % ((int)un_w.size())], sec_ch = -1;
vector<int> rep_e;
for(int i = 0; i < m; ++i) {
if(isAble(chosen, i))
rep_e.push_back(i);
}
if(rep_e.empty()) {
coloring(chosen, 1);
continue;
}
for(int c : rep_e) {
if(type[c]) {
sec_ch = c;
break;
}
}
if(sec_ch != -1) {
w.erase(find(w.begin(), w.end(), chosen));
w.push_back(sec_ch);
int res1 = count_common_roads(w);
if(res0 == res1) coloring(chosen, type[sec_ch]);
else coloring(chosen, 1 + (res0 < res1));
} else {
for(int c : rep_e) {
if(ds.find(c) != ds.find(chosen)) {
sec_ch = c;
break;
}
}
if(sec_ch == -1) continue;
w.erase(find(w.begin(), w.end(), chosen));
w.push_back(sec_ch);
int res1 = count_common_roads(w);
if(res0 == res1) ds.merge(chosen, sec_ch);
else {
if(res0 < res1)
coloring(chosen, 2),
coloring(sec_ch, 1);
else
coloring(chosen, 1),
coloring(sec_ch, 2);
}
}
}
vector<int> r;
for(int i = 0; i < m; i++) {
if(type[i] == 1)
r.push_back(i);
}
return r;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
correct |
| 2 |
Incorrect |
1 ms |
340 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
