#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 500 + 10;
int n, m, h[maxn], par[maxn], dsu[maxn*maxn], edge[maxn*maxn][2];
vector<int> g[maxn], t[maxn];
vector<int> badedge;
vector<int> ans;
bool vis[maxn], mark[maxn];
int getpar(int v){
//debug(v, dsu[v]);
return (dsu[v] == -1? v: dsu[v] = getpar(dsu[v]));
}
void merge(int u, int v){
//debug("merge", u, v);
if ((u = getpar(u)) == (v = getpar(v))) return;
//debug(u, v);
if (u < v) swap(u, v);
dsu[v] = u;
}
void predfs(int v){
vis[v] = true;
for (auto x: g[v]){
int u = edge[x][0] ^ edge[x][1] ^ v;
if (!vis[u]){
t[v].push_back(x);
t[u].push_back(x);
ans.push_back(x);
// debug("add", x);
h[u] = h[v] + 1;
predfs(u);
}
else if (h[u] > h[v]){
badedge.push_back(x);
}
}
}
void dfs(int v, int p = -1){
//debug(v, p, h[v]);
par[v] = p;
for (auto x: t[v]){
//debug(x);
if (x == p) continue;
int u = edge[x][0] ^ edge[x][1] ^ v;
//debug(edge[x][0], edge[x][1], u);
h[u] = h[v] + 1;
dfs(u, x);
}
}
std::vector<int> find_roads(int _n, std::vector<int> u, std::vector<int> v) {
memset(dsu, -1, sizeof dsu);
n = _n;
m = u.size();
for (int i = 0; i < m; i++){
edge[i][0] = u[i];
edge[i][1] = v[i];
g[v[i]].push_back(i);
g[u[i]].push_back(i);
}
predfs(0);
//debug(ans.size(), badedge.size());
int res = count_common_roads(ans);
//debug(res);
for (auto x: badedge){
// debug(x);
assert(ans.size() == n-1);
dfs(0);
int v = edge[x][0], u = edge[x][1];
if (h[v] < h[u]) swap(u, v);
bool flg = false;
// debug(v, u);
while(v != u && getpar(x) < m){
int e = par[v];
// debug(e, x);
if (getpar(e) != getpar(x)){
// debug(0);
ans.erase(find(all(ans), e));
ans.push_back(x);
int tmp = count_common_roads(ans);
ans.pop_back();
ans.push_back(e);
if (tmp == res){
// debug(1);
merge(e, x);
}
else if (tmp < res){
// debug(2);
merge(e, m);
merge(x, m+1);
}
else{
// debug(3);
// debug("readd", e, x);
res = tmp;
merge(e, m+1);
ans.pop_back();
t[edge[e][0]].erase(find(all(t[edge[e][0]]), e));
t[edge[e][1]].erase(find(all(t[edge[e][1]]), e));
merge(x, m);
}
}
v = edge[e][0] ^ edge[e][1] ^ v;
}
// debug(x, getpar(x));
if (getpar(x) == m){
ans.push_back(x);
t[edge[x][0]].push_back(x);
t[edge[x][1]].push_back(x);
}
else{
merge(x, m+1);
}
}
//for (auto x: ans) debug(x);
return ans;
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from simurgh.cpp:2:
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:94:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
94 | assert(ans.size() == n-1);
| ~~~~~~~~~~~^~~~~~
simurgh.cpp:98:8: warning: unused variable 'flg' [-Wunused-variable]
98 | bool flg = false;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
2516 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
2516 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
2516 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1236 KB |
correct |
| 2 |
Runtime error |
2 ms |
2516 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
2516 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
