Submission #1016299

#TimeUsernameProblemLanguageResultExecution timeMemory
1016299hotboy2703Simurgh (IOI17_simurgh)C++17
100 / 100
103 ms6744 KiB
#include "simurgh.h" #include<bits/stdc++.h> using namespace std; using ll = int; #define pll pair <ll,ll> #define fi first #define se second #define MP make_pair #define sz(a) (ll((a).size())) #define BIT(mask,i) (((mask) >> (i))&1) #define MASK(i) (1LL << (i)) namespace TRUNG{ const ll MAXN = 510; ll n,m; ll ans[MAXN*MAXN]; vector <pll> g[MAXN]; bool sus[MAXN*MAXN]; ll in[MAXN],out[MAXN]; ll timeDFS; vector <pll> a; ll cnt_query; void dfs(ll u,ll p){ in[u] = ++timeDFS; for (auto tmp:g[u]){ ll v = tmp.fi,id = tmp.se; if (v==p)continue; dfs(v,u); } out[u] = timeDFS; } bool sus_edge(ll i,ll j){ ll x = a[i].fi; if (in[a[i].se] > in[x])x = a[i].se; // cout<<i<<' '<<j<<' '<<x<<endl; if ((in[x] <= in[a[j].fi] && in[a[j].fi] <= out[x])+(in[x] <= in[a[j].se] && in[a[j].se] <= out[x])==1)return 1; return 0; } namespace DSU{ ll dsu[MAXN]; void init(){ memset(dsu,-1,sizeof dsu); } ll f(ll x){ if (dsu[x] < 0)return x; return (dsu[x] = f(dsu[x])); } void join(ll x,ll y){ x = f(x),y = f(y); if (x!=y){ if (dsu[x] > dsu[y])swap(x,y); dsu[x] += dsu[y]; dsu[y] = x; } } } bitset <MAXN> bs[MAXN]; ll ind[MAXN][MAXN]; vector <ll> tree,extra; ll superior_count(vector <ll> all){ DSU::init(); for (auto x:all){ DSU::join(a[x].fi,a[x].se); } ll res = 0; for (auto x:tree){ if (DSU::f(a[x].fi) != DSU::f(a[x].se)){ DSU::join(a[x].fi,a[x].se); all.push_back(x); res-=ans[x]; } } assert(++cnt_query<=8000); res += count_common_roads(all); return res; } void solve(vector <ll> all,ll k){ if (k==0)return; if (sz(all) == 1){ ans[all[0]] = k; return; } ll mid = sz(all) / 2; vector <ll> L,R; for (ll i = 0;i < sz(all);i ++){ if (i < mid)L.push_back(all[i]); else R.push_back(all[i]); } ll cnt_L = superior_count(L); solve(L,cnt_L); solve(R,k-cnt_L); } } std::vector<int> find_roads(int N, std::vector<int> U, std::vector<int> V) { using namespace TRUNG; memset(ans,-1,sizeof ans); ll m = sz(U),n=N ; a.resize(m); for (ll i = 0;i < m;i ++)a[i] = MP(U[i],V[i]); DSU::init(); for (ll i = 0;i < m;i ++){ if (DSU::f(a[i].fi) != DSU::f(a[i].se)){sus[i] = 1;tree.push_back(i);} DSU::join(a[i].fi,a[i].se); } DSU::init(); for (ll i = 0;i < m;i ++){ if (sus[i])continue; if (DSU::f(a[i].fi) != DSU::f(a[i].se))extra.push_back(i); DSU::join(a[i].fi,a[i].se); } for (auto id:tree){ g[a[id].fi].push_back(MP(a[id].se,id)); g[a[id].se].push_back(MP(a[id].fi,id)); } dfs(0,0); // cout<<in[4]<<' '<<out[4]<<' '<<in[1]<<' '<<out[1]<<endl; // for (auto x:tree)cout<<x<<' '; // cout<<'\n'; // for (auto x:extra)cout<<x<<' '; // cout<<'\n'; // cout<<sus_edge(4,7)<<endl; ll cur = count_common_roads(tree); assert(++cnt_query<=8000); for (auto id:tree){ // cout<<id<<endl; if (ans[id] != -1)continue; for (auto x:extra){ if (sus_edge(id,x)){ // cout<<"WOW "<<x<<' '<<id<<endl; auto cal = [&](ll y){ vector <ll> tmp; tree.push_back(x); for (auto sss:tree)if (sss != y)tmp.push_back(sss); tree.pop_back(); assert(++cnt_query<=8000); // cout<<"CAL "<<y<<": "; // for (auto z:tmp)cout<<z<<' '; // cout<<endl; ll res = count_common_roads(tmp); // cout<<"VAL "<<res<<endl; return res; }; vector <ll> cycle; for (auto y:tree){ if (sus_edge(y,x)){ cycle.push_back(y); } } // for (auto y:cycle)cout<<y<<' '; // cout<<endl; ll sum = -1; if (ans[x] != -1)sum = ans[x] + cur; for (auto y:cycle){ if (ans[y] != -1 && sum == -1){ sum = cal(y) + ans[y]; break; } } if (sum==-1){ vector <ll> com(sz(cycle)); for (ll j = 0;j < sz(cycle);j ++){ com[j] = cal(cycle[j]); if (com[j] < cur)sum = cur; if (com[j] > cur)sum = cur+1; // cout<<cycle[j]<<' '<<com[j]<<endl; } if (sum == -1)sum = cur; for (ll j = 0;j < sz(cycle);j ++){ ans[cycle[j]] = sum - com[j]; } ans[x] = sum - cur; } else{ for (auto y:cycle)if (ans[y] == -1){ ans[y] = sum - cal(y); } ans[x] = sum - cur; } break; } } if (ans[id] == -1)ans[id] = 1; } // for (ll j = 0;j < m;j ++)cout<<ans[j]<<' '; // cout<<endl; for (ll j = 0;j < m;j ++){ pll x = a[j]; ind[x.fi][x.se]=ind[x.se][x.fi]=j; if (ans[j] == -1)bs[x.fi][x.se] = bs[x.se][x.fi] = 1; } while (true){ bitset <MAXN> rem; rem.set(); bitset <MAXN> tmp; vector <ll> cur; for (ll i = 0;i < n;i ++){ if (rem[i]){ queue <ll> q; q.push(i); rem[i] = 0; while (!q.empty()){ ll u = q.front(); q.pop(); tmp = rem & bs[u]; for (ll v = tmp._Find_first();v < n;v = tmp._Find_next(v)){ cur.push_back(ind[u][v]); bs[u][v] = bs[v][u] = 0; q.push(v); rem[v] = 0; } } } } if (!sz(cur))break; // cout<<sz(cur)<<' '<<cur[0]<<endl; solve(cur,superior_count(cur)); } vector <ll> r; for (ll i = 0;i < m;i ++)if (ans[i]==1)r.push_back(i); // assert(cnt_query<=8000); // count_common_roads return r; }

Compilation message (stderr)

simurgh.cpp: In function 'void TRUNG::dfs(ll, ll)':
simurgh.cpp:26:27: warning: unused variable 'id' [-Wunused-variable]
   26 |             ll v = tmp.fi,id = tmp.se;
      |                           ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...