Submission #797388

#TimeUsernameProblemLanguageResultExecution timeMemory
797388alvingogoAncient Books (IOI17_books)C++14
50 / 100
240 ms36344 KiB
#include "books.h" #include <bits/stdc++.h> #pragma GCC optimize("Ofast") #define AquA cin.tie(0);ios_base::sync_with_stdio(0); #define fs first #define sc second #define p_q priority_queue using namespace std; typedef long long ll; struct DSU{ vector<int> bo; void init(int x){ bo.resize(x); iota(bo.begin(),bo.end(),0); } int find(int x){ return bo[x]==x?x:bo[x]=find(bo[x]); } int merge(int x,int y){ x=find(x); y=find(y); if(x==y){ return 0; } bo[x]=y; return 1; } }dsu; ll minimum_walk(vector<int> p, int s) { ll ans=0; int n=p.size(); dsu.init(n); vector<int> bo(n,-1),k(n),pre(n); for(int i=0;i<n;i++){ if(bo[i]==-1){ pre[i]++; int cnt=0; int f=0; for(int x=i;bo[x]==-1;x=p[x]){ dsu.merge(x,i); bo[x]=i; cnt++; f=max(f,x); } if(cnt>=2){ k[i]=1; } pre[f]--; } ans+=abs(i-p[i]); } for(int i=1;i<n;i++){ pre[i]+=pre[i-1]; } k[bo[s]]=1; for(int i=0;i+1<n;i++){ if(pre[i]){ dsu.merge(i,i+1); } } int mn=-1; vector<pair<int,pair<int,int> > > e; for(int i=0;i<n;i++){ if(k[bo[i]]){ if(mn!=-1){ e.push_back({i-mn,{i,mn}}); } mn=i; } } sort(e.begin(),e.end()); for(auto h:e){ ans+=2*dsu.merge(h.sc.fs,h.sc.sc)*h.fs; } return ans; }
#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...