#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define fr first
#define sc second
//#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
const int nmax = 505;
int N, m, h[nmax], ansT, royal[nmax*nmax], lipsa[nmax*nmax], pardsu[nmax];
vector<int>T;
pair<int,int>low[nmax], p[nmax];
vector<pair<int,int>>nod[nmax];
bitset<nmax>viz;
void dfstree(int s, int lvl, int par){
viz[s] = 1;
h[s] = lvl;
for(auto it : nod[s]){
if(!viz[it.fr]){
T.push_back(it.sc);
dfstree(it.fr, lvl + 1, s);
p[it.fr].fr = s;
p[it.fr].sc = it.sc;
if(low[it.fr] < low[s]){
low[s] = low[it.fr];
}
}
}
for(auto it : nod[s]){
if(viz[it.fr] && it.fr != par && h[it.fr] < low[s].fr){
low[s].fr = h[it.fr];
low[s].sc = it.sc;
}
}
}
void calc(vector<int>vecc, int indx){
reverse(all(vecc));
vector<int>ask;
vector<pair<int,int>>Queries;
for(auto it : vecc){
if(royal[it] == -1){
ask.clear();
for(auto it1 : T){
if(it1 != it){
ask.push_back(it1);
}
}
ask.push_back(indx);
lipsa[it] = count_common_roads(ask);
Queries.push_back({lipsa[it], it});
}
}
Queries.push_back({ansT, indx});
sort(all(Queries));
if(Queries[0].fr == Queries.back().fr){
if(Queries.size() == vecc.size() + 1){
for(auto it : vecc) royal[it] = 0;
}
else{
ask.clear();
for(auto it : T){
if(it != vecc[0]){
ask.push_back(it);
}
}
ask.push_back(indx);
int lol = count_common_roads(ask);
for(auto it : Queries){
if(it.fr == lol){
if(royal[vecc[0]] == 1) royal[it.sc] = 1;
else royal[it.sc] = 0;
}
else{
if(royal[vecc[0]] == 0) royal[it.sc] = 1;
else royal[it.sc] = 0;
}
}
}
}
else{
for(auto it : Queries){
if(it.fr == Queries.back().fr){
royal[it.sc] = 0;
}
else{
royal[it.sc] = 1;
}
}
}
}
void dfs2(int s){
viz[s] = 1;
for(auto it : nod[s]){
if(it.sc == low[s].sc && low[s].fr < h[s]){
int curr = s;
vector<int>vecc;
while(h[curr] != h[it.fr]){
vecc.push_back(p[curr].sc);
curr = p[curr].fr;
}
calc(vecc, it.sc);
}
}
for(auto it : nod[s]){
if(!viz[it.fr]){
dfs2(it.fr);
}
}
}
int findpar(int x){
if(x != pardsu[x]){
pardsu[x] = findpar(pardsu[x]);
}
return pardsu[x];
}
void unite(int x, int y){
x = findpar(x);
y = findpar(y);
pardsu[x] = y;
}
void make_bs(int s, vector<int>&u, vector<int>&v){
vector<pair<int,pair<int,int>>>vecc;
for(auto it : nod[s]){
if(it.fr != p[s].fr && h[it.fr] < h[s]){
vecc.push_back({h[it.fr], {it.fr, it.sc}});
}
}
sort(all(vecc));
for(int i=0;i<N;i++) pardsu[i] = i;
vector<int>ask;
for(auto it : vecc){
ask.push_back(it.sc.sc);
unite(s, it.sc.fr);
}
int curr = 0;
for(auto it : T){
int x = u[it];
int y = v[it];
x = findpar(x);
y = findpar(y);
if(x != y){
pardsu[x] = y;
ask.push_back(it);
curr -= royal[it];
}
}
curr += count_common_roads(ask);
int l = 0;
int r = (int)vecc.size()-1;
for(int i=1;i<=curr;i++){
int ok = 0;
while(l <= r){
ask.clear();
int mid = l + (r - l) / 2;
for(int i=0;i<N;i++) pardsu[i] = i;
for(int i=0;i<=mid;i++){
ask.push_back(vecc[i].sc.sc);
unite(s, vecc[i].sc.fr);
}
curr = 0;
for(auto it : T){
int x = u[it];
int y = v[it];
x = findpar(x);
y = findpar(y);
if(x != y){
pardsu[x] = y;
ask.push_back(it);
curr -= royal[it];
}
}
curr += count_common_roads(ask);
if(curr >= i){
ok = mid;
r = mid - 1;
}
else{
l = mid + 1;
}
}
royal[vecc[ok].sc.sc] = 1;
l = ok + 1;
}
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
m = (int)u.size();
N = n;
for(int i=0;i<m;i++){
royal[i] = -1;
}
for(int i=0;i<n;i++){
low[i].fr = n + 1;
low[i].sc = -1;
}
for(int i=0;i<m;i++){
nod[u[i]].push_back({v[i], i});
nod[v[i]].push_back({u[i], i});
}
p[0].fr = -1;
dfstree(0, 1, -1);
ansT = count_common_roads(T);
viz.reset();
dfs2(0);
for(auto it : T){
if(royal[it] == -1) royal[it] = 1;
}
for(int i=1;i<n;i++){
make_bs(i, u, v);
}
for(int i=0;i<m;i++){
if(royal[i] == -1){
royal[i] = 0;
}
}
vector<int>answer;
for(int i=0;i<m;i++){
if(royal[i] == 1)answer.push_back(i);
}
return answer;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
correct |
| 2 |
Incorrect |
1 ms |
332 KB |
WA in grader: NO |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
WA in grader: NO |
| 2 |
Halted |
0 ms |
0 KB |
- |
