Submission #870802

#	Time	Username	Problem	Language	Result	Execution time	Memory
870802		HuyQuang_re_Zero	Wombats (IOI13_wombats)	C++14	100 / 100	8304 ms	197900 KiB

wombats

#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;
      |                          ^~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 24 / 24