| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1093894 | azberjibiou | Simurgh (IOI17_simurgh) | C++17 | 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"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=505;
const int mxM=10000;
const int mxK=60;
const ll INF=1e18;
struct uf{
int p[mxN];
void init(int n){for(int i=0;i<n;i++) p[i]=i;}
int fp(int a){return p[a]==a ? a : p[a]=fp(p[a]);}
void mrg(int a, int b){p[fp(a)]=fp(b);}
};
int N;
vector <int> v[mxN];
vector <pii> E;
int num[mxN][mxN];
int gold[mxN][mxN];
//dfs
bool Chk[mxN];
int dep[mxN], par[mxN];
vector <int> tree;
void init(){
for(int i=0;i<mxN;i++) v[i].clear();
E.clear();
for(int i=0;i<mxN;i++) for(int j=0;j<mxN;j++) num[i][j]=-1, gold[i][j]=-1;
for(int i=0;i<mxN;i++) Chk[i]=false, dep[i]=0, par[i]=0, sub[i].clear();
tree.clear();
}
void dfs(int now){
Chk[now]=true;
sub[now].push_back(now);
for(int nxt : v[now]) if(!Chk[nxt]){
dep[nxt]=dep[now]+1;
par[nxt]=now;
tree.push_back(num[nxt][now]);
dfs(nxt);
for(int x : sub[nxt]) sub[now].push_back(x);
}
}
uf U_qry;
int make_query(vector <int> qry, bool proc){ // qry does not have a cycle!, proc: remove value of edges out of qry
vector <int> res=qry;
U_qry.init(N);
for(int x : qry) U_qry.mrg(E[x].fi, E[x].se);
for(int x : tree){
auto [now1, now2]=E[x];
if(U_qry.fp(now1)!=U_qry.fp(now2)){
res.push_back(x);
U_qry.mrg(now1, now2);
}
}
int val=count_common_roads(res);
if(proc){
for(int i=qry.size();i<res.size();i++){
auto [now1, now2]=E[res[i]];
if(gold[now1][now2]==1) val--;
}
}
return val;
}
vector <int> minu(vector <int> gph, int x){
vector <int> res;
for(int y : gph) if(y!=x) res.push_back(y);
return res;
}
void check_cycle(vector <int> cyc){
vector <int> qres(cyc.size(), -1);
int know=-1;
for(int x : cyc) if(gold[E[x].fi][E[x].se]!=-1) know=x;
int tot=-1;
if(know!=-1){
tot=make_query(minu(cyc, know), false)+gold[E[know].fi][E[know].se];
}
for(int i=0;i<cyc.size();i++){
auto [now1, now2]=E[cyc[i]];
if(gold[now1][now2]==-1) qres[i]=make_query(minu(cyc, cyc[i]), false);
}
if(know==-1){
int sum=0;
for(int i=0;i<cyc.size();i++) sum+=qres[i];
sum/=cyc.size();
tot=sum+1;
}
for(int i=0;i<cyc.size();i++){
auto [now1, now2]=E[cyc[i]];
if(gold[now1][now2]==-1){
if(qres[i]==tot) gold[now1][now2]=gold[now2][now1]=0;
else gold[now1][now2]=gold[now2][now1]=1;
}
}
}void make_spanning_tree(){
dfs(0);
sort(all(tree), [](int a, int b){return min(dep[E[a].fi], dep[E[a].se])>min(dep[E[b].fi], dep[E[b].se]);});
for(int ednum : tree){
auto [now1, now2]=E[ednum];
if(dep[now1]>dep[now2]) swap(now1, now2);
if(gold[now1][now2]!=-1) continue;
int down=-1, up=-1;
for(int x : sub[now2]) for(int y : v[x]) if(dep[y]<=dep[now1]) down=x, up=y;
if(up==-1){
gold[now1][now2]=gold[now2][now1]=1;
continue;
}
vector <int> cyc;
int pnt=down;
while(pnt!=up){
cyc.push_back(num[pnt][par[pnt]]);
pnt=par[pnt];
}
cyc.push_back(num[down][up]);
check_cycle(cyc);
}
}
vector <int> rng(vector <int> s, pii lr){
vector <int> res;
for(int i=lr.fi;i<=lr.se;i++) res.push_back(s[i]);
return res;
}
void find_gold(){
for(int i=0;i<N;i++){
vector <int> ct;
for(int j=i+1;j<N;j++){
if(num[i][j]!=-1 && gold[i][j]==-1) ct.push_back(num[i][j]);
}
while(ct.size() && make_query(ct, true)!=0){
int s=0, e=ct.size()-1;
while(s!=e){
int mid=(s+e)/2;
if(make_query(rng(ct, pii(s, mid)), true)==0) s=mid+1;
else e=mid;
}
auto [now1, now2]=E[ct[s]];
gold[now1][now2]=gold[now2][now1]=1;
ct=minu(ct, ct[s]);
}
}
}
std::vector<int> find_roads(int n, std::vector<int> a, std::vector<int> b) {
N=n;
init();
for(int i=0;i<a.size();i++){
int t1=a[i], t2=b[i];
v[t1].push_back(t2);
v[t2].push_back(t1);
E.emplace_back(t1, t2);
num[t1][t2]=num[t2][t1]=i;
}
make_spanning_tree();
find_gold();
vector<int> r;
for(int i=0;i<N;i++) for(int j=i+1;j<N;j++) if(gold[i][j]==1) r.push_back(num[i][j]);
return r;
}