#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef double dd;
typedef pair<ll , ll> ii;
typedef tuple < ll, ll, ll > tp;
#define ff first
#define ss second
#define pb push_back
#define in insert
#define mem(a , b) memset(a, b ,sizeof(a))
const ll N = 505;
vector < ii > v[N];
vector < tuple < ll , ll, ll > > e, Nice;
ll n, col[N * N], par[N], vis[N], edge[N], deg[N], D[N];
void dfs(ll node, ll shit){
vis[node] = 1;
for(auto [u, i] : v[node]){
if(!vis[u]){
edge[u] = i;
D[u] = D[node] + 1;
par[u] = node;
Nice.pb({node, u, i});
dfs(u, 1);
}
}
}
ll Norm = 0;
void dfs(ll node){
vis[node] = 1;
for(auto [u, i] : v[node]){
if(!vis[u]){
dfs(u);
}else{
if(D[u] > D[node]) continue;
vector < ll > edges, extra;
ll cur = node;
while(cur != u){
if(col[edge[cur]] == -1) edges.pb(edge[cur]);
else extra.pb(edge[cur]);
cur = par[cur];
}
if(edges.size()){
vector < ii > val; val.pb({Norm, i});
if(extra.size()){
edges.pb(extra[0]);
}
for(auto x : edges){
vector < ll > query;
for(auto [_ , __, j] : Nice){
if(j == x) query.pb(i);
else query.pb(j);
}
val.pb({count_common_roads(query), x});
}
sort(val.begin(), val.end());
if(val[0].ff == val.back().ff){
if(extra.size()){
for(auto [_, x] : val) col[x] = col[extra[0]];
}else{
for(auto [_, x] : val) col[x] = 0;
}
}else{
for(auto [_ , x] : val){
col[x] = (_ == val[0].ff);
}
}
}
}
}
return;
}
struct DSU{
vector < int > par;
void start(int n){
par.resize(n + 1);
for(int i = 0; i <= n; i++) par[i] = i;
}
int find(int a){
if(a == par[a]) return a;
return par[a] = find(par[a]);
}
void merge(int x, int y){
x = find(x); y = find(y);
if(x == y) return;
par[x] = y;
return;
}
};
ll plag(vector < tuple < ll , ll, ll > > E){
DSU T; T.start(n);
vector < ll > golden;
for(auto [x, y, i] : E){
T.merge(x, y);
golden.pb(i);
}
ll S = 0;
for(auto [x, y, i] : Nice){
if(T.find(x) == T.find(y)) continue;
T.merge(x, y);
golden.pb(i);
S += col[i];
}
return count_common_roads(golden) - S;
}
std::vector<int> find_roads(int _n, std::vector<int> _u, std::vector<int> _v) {
n = _n;
for(ll i = 0; i < _u.size(); i++){
e.pb({_u[i], _v[i], i});
}
for(auto [x, y, i] : e){
v[x].pb({y, i});
v[y].pb({x, i});
}
mem(col, -1);
mem(vis, 0);
par[0] = -1;
D[0] = 0;
dfs(0, 1);
vector < ll > golden;
for(auto [x, y, i] : Nice){
golden.pb(i);
}
Norm = count_common_roads(golden);
mem(vis, 0);
dfs(0);
ll Sum = 0;
for(auto [x, y, i] : Nice){
if(col[i] == -1){
col[i] = 1;
}
Sum += col[i];
}
assert(Norm == Sum);
queue < ll > q;
for(ll i = 0; i < n; i++){
vector < tuple < ll , ll , ll > > dump;
for(auto [u, j] : v[i]){
dump.pb({i, u, j});
}
deg[i] = plag(dump);
if(deg[i] == 1) q.push(i);
}
vector < ll > royal;
mem(vis, 0);
for(ll itr = 0; itr < n - 1; itr++){
ll node = q.front(); q.pop();
vis[node] = 1;
vector < tuple < ll , ll , ll > > E;
for(auto [u, i] : v[node]){
if(vis[u] == 1) continue;
E.push_back({node, u, i});
}
ll l = 0, r = E.size() - 1, k = 0;
while(l <= r){
ll m = (l + r) / 2;
vector < tuple < ll , ll , ll > > dump;
for(ll i = 0; i <= m; i++) dump.pb(E[i]);
if(plag(dump)){
k = m;
r = m - 1;
}else{
l = m + 1;
}
}
auto [_, nxt, i] = E[k];
royal.pb(i);
deg[nxt]--;
//cout << node << ' ' << nxt << '\n';
if(deg[nxt] == 1) q.push(nxt);
}
return royal;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:121:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(ll i = 0; i < _u.size(); i++){
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1236 KB |
correct |
| 2 |
Correct |
1 ms |
1236 KB |
correct |
| 3 |
Correct |
1 ms |
1236 KB |
correct |
| 4 |
Correct |
1 ms |
1236 KB |
correct |
| 5 |
Runtime error |
2 ms |
2516 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1236 KB |
correct |
| 2 |
Correct |
1 ms |
1236 KB |
correct |
| 3 |
Correct |
1 ms |
1236 KB |
correct |
| 4 |
Correct |
1 ms |
1236 KB |
correct |
| 5 |
Runtime error |
2 ms |
2516 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1236 KB |
correct |
| 2 |
Correct |
1 ms |
1236 KB |
correct |
| 3 |
Correct |
1 ms |
1236 KB |
correct |
| 4 |
Correct |
1 ms |
1236 KB |
correct |
| 5 |
Runtime error |
2 ms |
2516 KB |
Execution killed with signal 6 |
| 6 |
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 |
Correct |
1 ms |
1236 KB |
correct |
| 3 |
Correct |
1 ms |
1236 KB |
correct |
| 4 |
Correct |
1 ms |
1236 KB |
correct |
| 5 |
Runtime error |
2 ms |
2516 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
