Submission #870802

#TimeUsernameProblemLanguageResultExecution timeMemory
870802HuyQuang_re_ZeroWombats (IOI13_wombats)C++14
100 / 100
8304 ms197900 KiB
#include <bits/stdc++.h> #define ll long long #define db long double #define II pair <ll,ll> #define III pair <ll,II> #define IV pair <vector <int>,vector <int> > #define fst first #define snd second #define BIT(x,i) ((x>>i)&1) #define pi acos(-1) #define to_radian(x) (x*pi/180.0) #define to_degree(x) (x*180.0/pi) #define Log(x) (31-__builtin_clz((int)x)) #define LogLL(x) (63-__builtin_clzll((ll)x)) #define N 202 #include "wombats.h" using namespace std; int n,m,H[5001][202],V[5001][202],i,j; const ll len=15; struct Block { int l,r,dis[N][N]; void solve(int y1,Block &a,Block &b,int l,int r,int u,int v) { if(l>r) return ; int mid=(l+r)>>1,pos; dis[y1][mid]=2e9; for(int i=u;i<=v;i++) { int k=V[a.r][i]; if(dis[y1][mid]>a.dis[y1][i]+b.dis[i][mid]+k) { dis[y1][mid]=a.dis[y1][i]+b.dis[i][mid]+k; pos=i; } } solve(y1,a,b,l,mid-1,u,pos); solve(y1,a,b,mid+1,r,pos,v); } void comp(Block &a,Block &b) { for(int i=1;i<=m;i++) solve(i,a,b,1,m,1,m); } } ; Block operator + (Block a,Block b) { Block res; res.l=a.l; res.r=b.r; res.comp(a,b); return res; } Block Cal_Row(int x) { Block res; res.l=res.r=x; for(int y1=1;y1<=m;y1++) { res.dis[y1][y1]=0; for(int y2=y1+1;y2<=m;y2++) res.dis[y1][y2]=res.dis[y2][y1]=res.dis[y1][y2-1]+H[x][y2-1]; } return res; } Block Recal(int l,int r) { Block res; res=Cal_Row(l); for(int i=l+1;i<=r;i++) res=res+Cal_Row(i); return res; } struct Interval_Tree { Block st[1024]; void build(int id,int l,int r) { if(r-l+1<=15) { st[id]=Recal(l,r); return ; } int mid=(l+r)>>1; build(id*2,l,mid); build(id*2+1,mid+1,r); st[id]=st[id*2]+st[id*2+1]; } void update(int id,int l,int r,int u) { if(u<l || u>r) return ; if(r-l+1<=15) { st[id]=Recal(l,r); return ; } int mid=(l+r)>>1; update(id*2,l,mid,u); update(id*2+1,mid+1,r,u); st[id]=st[id*2]+st[id*2+1]; } } IT; void Change_H(int x,int y,int k) { H[x][y]=k; IT.update(1,1,n,x); } void Change_V(int x,int y,int k) { V[x][y]=k; IT.update(1,1,n,x); } int Ans(int y1,int y2) { return IT.st[1].dis[y1][y2]; } void Take_information(int _n,int _m,int _H[5000][200],int _V[5000][200]) { n=_n; m=_m; for(i=1;i<=n;i++) for(j=1;j<m;j++) H[i][j]=_H[i-1][j-1]; for(i=1;i<n;i++) for(j=1;j<=m;j++) V[i][j]=_V[i-1][j-1]; IT.build(1,1,n); } /////////////////////////////////////////////////////////////////////////////////// void init(int R,int C,int _H[5000][200],int _V[5000][200]) { Take_information(R,C,_H,_V); } void changeH(int P,int Q,int W) { Change_H(P+1,Q+1,W); } void changeV(int P,int Q,int W) { Change_V(P+1,Q+1,W); } int escape(int V1,int V2) { return Ans(V1+1,V2+1); } /* int main() { freopen("wombats.inp","r",stdin); freopen("wombats.out","w",stdout); int n,m,i,j,H[202][200],V[202][200]; ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; for(i=0;i<n;i++) for(j=0;j<m-1;j++) cin>>H[i][j]; for(i=0;i<n-1;i++) for(j=0;j<m;j++) cin>>V[i][j]; init(n,m,H,V); int type; while(cin>>type) { if(type==1) { int P,Q,W; cin>>P>>Q>>W; changeH(P,Q,W); } else if(type==2) { int P,Q,W; cin>>P>>Q>>W; changeV(P,Q,W); } else { int V1,V2; cin>>V1>>V2; cout<<escape(V1,V2)<<'\n'; } } } */

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~
wombats.cpp: In member function 'void Block::solve(int, Block&, Block&, int, int, int, int)':
wombats.cpp:38:14: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |         solve(y1,a,b,l,mid-1,u,pos);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
wombats.cpp:29:22: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |         for(int i=u;i<=v;i++)
      |                     ~^~~
wombats.cpp:29:22: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |         for(int i=u;i<=v;i++)
      |                     ~^~~
wombats.cpp:29:22: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |         for(int i=u;i<=v;i++)
      |                     ~^~~
wombats.cpp:29:22: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |         for(int i=u;i<=v;i++)
      |                     ~^~~
wombats.cpp:29:22: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |         for(int i=u;i<=v;i++)
      |                     ~^~~
wombats.cpp:29:22: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |         for(int i=u;i<=v;i++)
      |                     ~^~~
wombats.cpp:29:22: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |         for(int i=u;i<=v;i++)
      |                     ~^~~
wombats.cpp:29:22: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |         for(int i=u;i<=v;i++)
      |                     ~^~~
wombats.cpp: In function 'Block operator+(Block, Block)':
wombats.cpp:38:14: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |         solve(y1,a,b,l,mid-1,u,pos);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
wombats.cpp:27:26: note: 'pos' was declared here
   27 |         int mid=(l+r)>>1,pos;
      |                          ^~~
wombats.cpp: In function 'Block Recal(int, int)':
wombats.cpp:38:14: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |         solve(y1,a,b,l,mid-1,u,pos);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
wombats.cpp:27:26: note: 'pos' was declared here
   27 |         int mid=(l+r)>>1,pos;
      |                          ^~~
wombats.cpp: In member function 'void Interval_Tree::build(int, int, int)':
wombats.cpp:38:14: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |         solve(y1,a,b,l,mid-1,u,pos);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
wombats.cpp:27:26: note: 'pos' was declared here
   27 |         int mid=(l+r)>>1,pos;
      |                          ^~~
wombats.cpp: In member function 'void Interval_Tree::update(int, int, int, int)':
wombats.cpp:38:14: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |         solve(y1,a,b,l,mid-1,u,pos);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
wombats.cpp:27:26: note: 'pos' was declared here
   27 |         int mid=(l+r)>>1,pos;
      |                          ^~~
#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...