oj.uz

Submission #870789

# Submission time Handle Problem Language Result Execution time Memory
870789 2023-11-09T05:50:48 Z HuyQuang_re_Zero Wombats (IOI13_wombats) C++14
37 / 100
 825 ms 262144 KB 
#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][N],V[5001][N],i,j;
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);
    }
} B[501];


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;
}


void Recal(int k)
{
    Block res;
    res=Cal_Row(B[k].l);
    for(int i=B[k].l+1;i<=B[k].r;i++) res=res+Cal_Row(i);
    B[k]=res;
}

struct Interval_Tree
{
    Block st[4*501];
    void build(int id,int l,int r)
    {
        if(l==r) { st[id]=B[l]; 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(l==r) { st[id]=B[l]; 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;
    Recal(x/10);
    IT.update(1,0,n/10,x/10);
}
void Change_V(int x,int y,int k)
{
    V[x][y]=k;
    Recal(x/10);
    IT.update(1,0,n/10,x/10);
}
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];
    for(i=1;i<=n;i++)
    {
        int k=i/10;
        if(B[k].l==0) B[k].l=i;
        B[k].r=i;
    }
    int cnt=0;
    for(i=0;i<=n/10;i++) Recal(i);
    IT.build(1,0,n/10);
}
///////////////////////////////////////////////////////////////////////////////////














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[N][200],V[N][200];
    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);
    string type;
    while(cin>>type)
    {
        if(type=="CH")
        {
            int P,Q,W;
            cin>>P>>Q>>W;
            changeH(P,Q,W);
        }
        else if(type=="CV")
        {
            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

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 function 'void Take_information(int, int, int (*)[200], int (*)[200])':
wombats.cpp:120:9: warning: unused variable 'cnt' [-Wunused-variable]
  120 |     int cnt=0;
      |         ^~~
wombats.cpp: In member function 'void Block::solve(int, Block&, Block&, int, int, int, int)':
wombats.cpp:37:14: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   37 |         solve(y1,a,b,l,mid-1,u,pos);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
wombats.cpp:28:22: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   28 |         for(int i=u;i<=v;i++)
      |                     ~^~~
wombats.cpp:28:22: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   28 |         for(int i=u;i<=v;i++)
      |                     ~^~~
wombats.cpp:28:22: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   28 |         for(int i=u;i<=v;i++)
      |                     ~^~~
wombats.cpp:28:22: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   28 |         for(int i=u;i<=v;i++)
      |                     ~^~~
wombats.cpp:28:22: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   28 |         for(int i=u;i<=v;i++)
      |                     ~^~~
wombats.cpp:28:22: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   28 |         for(int i=u;i<=v;i++)
      |                     ~^~~
wombats.cpp:28:22: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   28 |         for(int i=u;i<=v;i++)
      |                     ~^~~
wombats.cpp:28:22: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   28 |         for(int i=u;i<=v;i++)
      |                     ~^~~
wombats.cpp: In function 'Block operator+(Block, Block)':
wombats.cpp:37:14: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   37 |         solve(y1,a,b,l,mid-1,u,pos);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
wombats.cpp:26:26: note: 'pos' was declared here
   26 |         int mid=(l+r)>>1,pos;
      |                          ^~~
wombats.cpp: In function 'void Recal(int)':
wombats.cpp:37:14: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   37 |         solve(y1,a,b,l,mid-1,u,pos);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
wombats.cpp:26:26: note: 'pos' was declared here
   26 |         int mid=(l+r)>>1,pos;
      |                          ^~~
wombats.cpp: In member function 'void Interval_Tree::build(int, int, int)':
wombats.cpp:37:14: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   37 |         solve(y1,a,b,l,mid-1,u,pos);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
wombats.cpp:26:26: note: 'pos' was declared here
   26 |         int mid=(l+r)>>1,pos;
      |                          ^~~
wombats.cpp: In member function 'void Interval_Tree::update(int, int, int, int)':
wombats.cpp:37:14: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   37 |         solve(y1,a,b,l,mid-1,u,pos);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
wombats.cpp:26:26: note: 'pos' was declared here
   26 |         int mid=(l+r)>>1,pos;
      |                          ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 260708 KB Output is correct
2 Correct 292 ms 260432 KB Output is correct
3 Correct 367 ms 262144 KB Output is correct
4 Correct 310 ms 260596 KB Output is correct
5 Correct 301 ms 260704 KB Output is correct
6 Correct 1 ms 5468 KB Output is correct
7 Correct 1 ms 5468 KB Output is correct
8 Correct 1 ms 5468 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5468 KB Output is correct
2 Correct 1 ms 5468 KB Output is correct
3 Correct 1 ms 5468 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 3 ms 12636 KB Output is correct
6 Correct 3 ms 12484 KB Output is correct
7 Correct 4 ms 12636 KB Output is correct
8 Correct 3 ms 11868 KB Output is correct
9 Correct 3 ms 11868 KB Output is correct
10 Correct 3 ms 12636 KB Output is correct
11 Correct 56 ms 15108 KB Output is correct
12 Correct 3 ms 12636 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 16732 KB Output is correct
2 Correct 173 ms 16720 KB Output is correct
3 Correct 219 ms 17044 KB Output is correct
4 Correct 218 ms 16976 KB Output is correct
5 Correct 207 ms 16988 KB Output is correct
6 Correct 2 ms 5468 KB Output is correct
7 Correct 1 ms 5468 KB Output is correct
8 Correct 1 ms 5468 KB Output is correct
9 Correct 825 ms 16944 KB Output is correct
10 Correct 2 ms 9560 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 129 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 16728 KB Output is correct
2 Correct 181 ms 16872 KB Output is correct
3 Correct 214 ms 17052 KB Output is correct
4 Correct 259 ms 16984 KB Output is correct
5 Correct 220 ms 17044 KB Output is correct
6 Runtime error 147 ms 262144 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 16884 KB Output is correct
2 Correct 173 ms 16728 KB Output is correct
3 Correct 218 ms 16924 KB Output is correct
4 Correct 232 ms 17232 KB Output is correct
5 Correct 209 ms 16840 KB Output is correct
6 Runtime error 125 ms 262144 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -