#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;
const int N = 510;
const int M = 510 * 510 / 2;
int n, m;
int pset[N];
int deg[N];
int label[N][N];
int par[N], h[N];
int visit_edge[M];
bool visit[N];
vector<int> G[N];
vector<int> vtree;
int find(int u) {
return u == pset[u] ? u : pset[u] = find(pset[u]);
}
bool join(int u, int v) {
u = find(u), v = find(v), pset[u] = v; return u != v;
}
void dfs(int u) {
visit[u] = 1;
for (auto v : G[u]) {
if (visit[v]) continue;
vtree.push_back(label[u][v]);
par[v] = u, h[v] = h[u] + 1, dfs(v);
}
}
vector<int> find_roads(int _n, vector<int> u, vector<int> v) {
n = _n, m = u.size();
for (int i = 0; i < m; ++i) {
G[u[i]].push_back(v[i]);
G[v[i]].push_back(u[i]);
label[u[i]][v[i]] = label[v[i]][u[i]] = i;
}
dfs(0);
int val = count_common_roads(vtree);
for (int i = 0; i < m; ++i) {
if (h[u[i]] > h[v[i]]) swap(u[i], v[i]);
int cur = v[i];
vector<int> vec;
while (cur != u[i]) {
int tmp = cur; cur = par[cur];
vec.push_back(label[cur][tmp]);
}
bool flag = 0;
for (auto j : vec) flag |= !visit_edge[j];
if (!flag || vec.size() == 1) continue;
int id = -1;
for (auto j : vec) if (visit_edge[j]) id = j;
if (id == -1) {
for (auto j : vec) {
vector<int> ask = vtree;
for (auto &k : ask) if (k == j) k = i;
int tmp = count_common_roads(ask);
if (tmp != val) {
visit_edge[i] = (tmp > val) + 1;
visit_edge[j] = 3 ^ visit_edge[i];
// 1 : not loyal, 2 : loyal
}
}
if (!visit_edge[i]) visit_edge[i] = 1;
for (auto j : vec) {
if (!visit_edge[j]) visit_edge[j] = visit_edge[i];
}
}
else {
vector<int> ask = vtree;
for (auto &j : ask) if (j == id) j = i;
int tmp = count_common_roads(ask);
if (tmp == val) visit_edge[i] = visit_edge[id];
else visit_edge[i] = 3 ^ visit_edge[id];
for (auto j : vec) {
if (!visit_edge[j]) {
vector<int> ask = vtree;
for (auto &k : ask) if (k == j) k = i;
int tmp = count_common_roads(ask);
if (tmp == val) visit_edge[j] = visit_edge[i];
else visit_edge[j] = 3 ^ visit_edge[i];
}
}
}
}
for (auto i : vtree) {
if (!visit_edge[i]) visit_edge[i] = 2;
}
queue<int> qu;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) pset[j] = j;
vector<int> ask;
for (auto j : G[i]) {
join(i, j), ask.push_back(label[i][j]);
}
int cnt = 0;
for (auto j : vtree) {
if (join(u[j], v[j])) {
cnt += visit_edge[j] == 2, ask.push_back(j);
}
}
deg[i] = count_common_roads(ask) - cnt;
for (auto j : G[i]) deg[i] -= visit_edge[label[i][j]] == 2;
if (deg[i] == 1) qu.push(i);
}
while (qu.size()) {
int x = qu.front(); qu.pop();
if (deg[x] != 1) continue;
vector<int> vec;
for (auto i : G[x]) {
if (!visit_edge[label[x][i]]) {
vec.push_back(label[x][i]);
}
}
int l = 0, r = vec.size();
while (l < r) {
int mid = (l + r) >> 1;
for (int i = 0; i < n; ++i) pset[i] = i;
vector<int> ask;
int cnt = 0;
for (int i = l; i <= mid; ++i) {
int tmp = vec[i];
join(u[tmp], v[tmp]);
ask.push_back(tmp);
cnt += visit_edge[tmp] == 2;
}
for (auto i : vtree) {
if (join(u[i], v[i])) {
ask.push_back(i);
cnt += visit_edge[i] == 2;
}
}
int tmp = count_common_roads(ask);
if (tmp == cnt + 1) r = mid;
else l = mid + 1;
}
visit_edge[label[x][vec[l]]] = 2;
deg[vec[l]]--;
if (deg[vec[l]] == 1) qu.push(vec[l]);
}
vector<int> res;
for (int i = 0; i < m; ++i) {
if (visit_edge[i] == 2) res.push_back(i);
}
return res;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
396 KB |
WA in grader: NO |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
396 KB |
WA in grader: NO |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
396 KB |
WA in grader: NO |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
488 KB |
correct |
2 |
Incorrect |
2 ms |
488 KB |
WA in grader: NO |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
396 KB |
WA in grader: NO |
2 |
Halted |
0 ms |
0 KB |
- |