Submission #202423

#TimeUsernameProblemLanguageResultExecution timeMemory
202423gs18115Wombats (IOI13_wombats)C++14
100 / 100
9779 ms188596 KiB
#include"wombats.h" #include<iostream> #include<vector> #include<algorithm> #define ep emplace #define eb emplace_back #define fi first #define se second #define all(x) (x).begin(),(x).end() #define semicolon ; #define ryan bear using namespace std; typedef long long ll; typedef pair<int,int>pi; typedef pair<ll,ll>pl; const int inf=1e9+7; const ll INF=1e18+7; struct node { int l,r; int d[200][200]; }tr[1500]; int r,c; int opt[200][200]; inline void merge(node&m,node&x,node&y) { for(int i=0;i<c;i++) for(int j=0;j<c;j++) opt[i][j]=-1; int&o0=opt[0][0]=0; m.d[0][0]=x.d[0][o0]+y.d[0][o0]; for(int k=0;++k<c;) if(x.d[0][k]+y.d[k][0]<x.d[0][o0]+y.d[o0][0]) o0=k,m.d[0][0]=x.d[0][o0]+y.d[o0][0]; for(int i=1;i<c;i++) { int j=0; int&o=opt[i][j]=opt[i-1][j]; m.d[i][j]=x.d[i][o]+y.d[o][j]; for(int k=o;++k<c;) if(x.d[i][k]+y.d[k][j]<x.d[i][o]+y.d[o][j]) o=k,m.d[i][j]=x.d[i][o]+y.d[o][j]; } for(int j=1;j<c;j++) { int i=c-1; int&o=opt[i][j]=opt[i][j-1]; m.d[i][j]=x.d[i][o]+y.d[o][j]; for(int k=o;++k<c;) if(x.d[i][k]+y.d[k][j]<x.d[i][o]+y.d[o][j]) o=k,m.d[i][j]=x.d[i][o]+y.d[o][j]; } for(int l=-c;++l<c;) { for(int i=0;i<c;i++) { int j=i+l; if(j<0||j>=c||opt[i][j]!=-1) continue; int&o=opt[i][j]=opt[i][j-1]; m.d[i][j]=x.d[i][o]+y.d[o][j]; for(int k=o;++k<=opt[i+1][j];) if(x.d[i][k]+y.d[k][j]<x.d[i][o]+y.d[o][j]) o=k,m.d[i][j]=x.d[i][o]+y.d[o][j]; } } return; } vector<vector<int> >h,v; inline void init(int n,int s,int e) { node&x=tr[n]; node t,p; vector<int>ps(c,0); for(int i=1;i<c;i++) ps[i]=ps[i-1]+h[s][i-1]; for(int i=0;i<c;i++) for(int j=0;j<c;j++) x.d[i][j]=i>j?ps[i]-ps[j]:ps[j]-ps[i]; for(int r=s;r<e;r++) { p=x; for(int i=0;i<c;i++) for(int j=0;j<c;j++) p.d[i][j]+=v[r][j]; for(int i=1;i<c;i++) ps[i]=ps[i-1]+h[r+1][i-1]; for(int i=0;i<c;i++) for(int j=0;j<c;j++) t.d[i][j]=i>j?ps[i]-ps[j]:ps[j]-ps[i]; merge(x,p,t); } return; } int tct=0,rt; int init(int s,int e) { int cur=tct++; node&x=tr[cur]; if(e-s<15) { x.l=x.r=0; init(cur,s,e); return cur; } int m=(s+e)/2; x.l=init(s,m); x.r=init(m,e); merge(x,tr[x.l],tr[x.r]); return cur; } void ch(int n,int s,int e,int r) { if(s>r||e<r) return; node&x=tr[n]; if(e-s<15) { init(n,s,e); return; } int m=(s+e)/2; ch(x.l,s,m,r); ch(x.r,m,e,r); merge(x,tr[x.l],tr[x.r]); return; } void cv(int n,int s,int e,int r) { if(s>r||e<=r) return; node&x=tr[n]; if(e-s<15) { init(n,s,e); return; } int m=(s+e)/2; cv(x.l,s,m,r); cv(x.r,m,e,r); merge(x,tr[x.l],tr[x.r]); return; } void init(int R,int C,int H[5000][200],int V[5000][200]) { r=R; c=C; h.resize(r); for(int i=0;i<r;i++) for(int j=0;j<c-1;j++) h[i].eb(H[i][j]); v.resize(r-1); for(int i=0;i<r-1;i++) for(int j=0;j<c;j++) v[i].eb(V[i][j]); rt=init(0,r-1); return; } void changeH(int P,int Q,int W) { h[P][Q]=W; ch(rt,0,r-1,P); return; } void changeV(int P,int Q,int W) { v[P][Q]=W; cv(rt,0,r-1,P); return; } int escape(int V1,int V2) { return tr[rt].d[V1][V2]; }

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...