#include "simurgh.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<cassert>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second
int n, m, tm, base, esp[125010], pv[510], pe[510], tin[510];
bool vis[510];
pii edges[125010];
vector<int> ted;
vector<vector<int>> uns;
vector<pii> g[510];
void dfs(int v){
tin[v]=tm++;
vis[v]=true;
for(pii to:g[v]) if(!vis[to.F]){
pv[to.F]=v;
pe[to.F]=to.S;
ted.PB(to.S);
dfs(to.F);
}
}
int add_count(int r){
int cou=base;
vector<int> ask;
forn(i, r){
if(!uns[i].empty()) ask.PB(uns[i].back()), cou-=esp[ted[i]];
else ask.PB(ted[i]);
}
forsn(i, r, n-1) ask.PB(ted[i]);
return count_common_roads(ask) - cou;
}
void dfs2(int l, int r, int lv, int rv){
if(lv==rv) return;
if(r-l==1){
esp[uns[l].back()]=1;
return;
}
int mid = (l+r)>>1, value = add_count(mid);
dfs2(l, mid, lv, value);
dfs2(mid, r, value, rv);
}
vector<int> find_roads(int N, vector<int> u, vector<int> v) {
n=N; m=u.size();
forn(i, m){
g[u[i]].PB({v[i], i});
g[v[i]].PB({u[i], i});
edges[i]={u[i], v[i]};
esp[i]=-1;
}
dfs(0);
sort(ted.begin(), ted.end());
base = count_common_roads(ted);
uns.resize(ted.size());
forn(i, m){
int a = edges[i].F, b = edges[i].S, know=-1;
if(tin[a]<tin[b]) swap(a, b);
if(pv[a]==b) continue;
uns[lower_bound(ted.begin(), ted.end(), pe[a]) - ted.begin()].PB(i);
vector<int> ed, res;
int cur=a;
while(cur!=b){
int e = pe[cur];
if(esp[e]!=-1) know=e;
else{
vector<int> tmp;
for(int el:ted) if(el!=e) tmp.PB(el);
tmp.PB(i);
ed.PB(e);
res.PB(count_common_roads(tmp));
}
cur = pv[cur];
}
if(know==-1){
int mn = *min_element(res.begin(), res.end());
mn = min(mn, base);
forn(j, ed.size()) esp[ed[j]]=(res[j]==mn);
}
else{
vector<int> tmp;
for(int el:ted) if(el!=know) tmp.PB(el);
tmp.PB(i);
int value = count_common_roads(tmp);
forn(j, ed.size()) esp[ed[j]]=esp[know]^(res[j]!=value);
}
}
for(int e:ted) if(esp[e]==-1) esp[e]=1;
bool cont=true;
while(cont){
int rv = add_count(n-1);
dfs2(0, n-1, 0, rv);
cont=false;
forn(i, n-1){
if(!uns[i].empty()) uns[i].pop_back();
cont|=!uns[i].empty();
}
}
vector<int> ret;
forn(i, m) if(esp[i]==1) ret.PB(i);
assert((int)ret.size()==n-1);
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
correct |
| 2 |
Correct |
0 ms |
212 KB |
correct |
| 3 |
Correct |
1 ms |
212 KB |
correct |
| 4 |
Correct |
1 ms |
212 KB |
correct |
| 5 |
Correct |
1 ms |
316 KB |
correct |
| 6 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
correct |
| 2 |
Correct |
0 ms |
212 KB |
correct |
| 3 |
Correct |
1 ms |
212 KB |
correct |
| 4 |
Correct |
1 ms |
212 KB |
correct |
| 5 |
Correct |
1 ms |
316 KB |
correct |
| 6 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
correct |
| 2 |
Correct |
0 ms |
212 KB |
correct |
| 3 |
Correct |
1 ms |
212 KB |
correct |
| 4 |
Correct |
1 ms |
212 KB |
correct |
| 5 |
Correct |
1 ms |
316 KB |
correct |
| 6 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
correct |
| 2 |
Correct |
0 ms |
212 KB |
correct |
| 3 |
Incorrect |
66 ms |
4972 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
correct |
| 2 |
Correct |
0 ms |
212 KB |
correct |
| 3 |
Correct |
1 ms |
212 KB |
correct |
| 4 |
Correct |
1 ms |
212 KB |
correct |
| 5 |
Correct |
1 ms |
316 KB |
correct |
| 6 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 7 |
Halted |
0 ms |
0 KB |
- |
