| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 134659 | dvdg6566 | Ancient Books (IOI17_books) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
#define pb emplace_back
#define mp make_pair
#define f first
#define s second
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define MAXN 300
int N,a,b;
vpi V[MAXN];
vpi edgeList;
vi res,cur;
vpi tmp;
int p[MAXN];
int lowlink[MAXN], depth[MAXN];
int par(int x){return (x==p[x])?x:p[x] = par(p[x]);}
vi bridges;
void dfs(int x,int p){
// cout<<"DFS "<<x<<' '<<p<<'\n';
lowlink[x] = depth[x];
for (auto v : V[x])if(v.f!=p){
if (depth[v.f] != -1){
lowlink[x] = min(lowlink[x], lowlink[v.f]);
continue;
}
depth[v.f] = depth[x]+1;
dfs(v.f,x);
lowlink[x] = min(lowlink[x], lowlink[v.f]);
}
}
bool isBridge(int x, int y){
if (lowlink[x]<=depth[y]&&depth[x]>depth[y])return 0;
if (lowlink[y]<=depth[x]&&depth[y]>depth[x])return 0;
// cout<<x<<' '<<y<<'\n';
return 1;
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
N=n;
for (int i=0;i<SZ(u);++i){
a=u[i];b=v[i];
V[a].pb(b,i);V[b].pb(a,i);
edgeList.pb(a,b);
}
a=1;
memset(depth,-1,sizeof(depth));
depth[0]=0;
dfs(0,0);
// for (int i=0;i<N;++i)cout<<depth[i]<<' '<<lowlink[i]<<'\n';
if (N <= 240){
for (int i=0;i<SZ(u);++i){
int a=edgeList[i].f;
int b=edgeList[i].s;
if (isBridge(a,b))bridges.pb(i);
}
// for (auto i : bridges)cout<<i<<'\n';
if (SZ(bridges) == N-1)return bridges;
for (int i=0;i<N;++i){
// We want to find all edges with index to a bigger node
for (int j=0;j<N;++j)p[j]=j;
cur.clear();
tmp.clear();
for (auto it : bridges){
cur.pb(it);
p[par(edgeList[it].f)] = par(edgeList[it].s);
}
for (int j=0;j<SZ(edgeList);++j){
pi it = edgeList[j];
if (it.f == i || it.s == i)continue;
if (par(it.f) == par(it.s))continue;
p[par(it.f)] = par(it.s);
cur.pb(j);
}
for (auto x : V[i]){
if (isBridge(i,x.f))continue;
if (i>x.f)continue;
cur.pb(x.s);
// for (auto i : cur)cout<<i<<' ' ;cout<<'\n';
int t = count_common_roads(cur);
tmp.pb(x.s,t);
cur.pop_back();
}
// cout<<"Current "<<i<<'\n';
// for (auto x : tmp)cout<<x.f<<' '<<x.s<<'\n';
int hh = 0;
// cout<<"V:";for (auto v:res)cout<<v<<' ';cout<<'\n';
bool gay=1;
for (auto t : res){
pi it = edgeList[t];
if (it.f == i || it.s == i){
cur.pb(t);
hh = count_common_roads(cur);
gay=0;
break;
}
}
if (gay){
int ll = 0;
for (auto x:tmp)ll = max(ll,x.s);
for (auto x :tmp)if(x.s==ll)res.pb(x.f);
continue;
}
for (auto x : tmp){
if (x.s == hh)res.pb(x.f);
}
// for (auto x :tmp)cout<<x.f<<' '<<x.s<<'\n';
// for (auto x:res)cout<<x<<' ';cout<<'\n';
}
for (auto i : bridges)res.pb(i);
sort(ALL(res));
res.resize(unique(ALL(res)) - res.begin());
// assert(SZ(res) == N-1);
return res;
}
assert(SZ(u) == N*(N-1)/2);
}