oj.uz

Submission #870803

# Submission time Handle Problem Language Result Execution time Memory
870803 2023-11-09T07:19:39 Z HuyQuang_re_Zero Wombats (IOI13_wombats) C++14
100 / 100
 11545 ms 107540 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][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<=20) { 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<=20) { 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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 101612 KB Output is correct
2 Correct 298 ms 101364 KB Output is correct
3 Correct 338 ms 102996 KB Output is correct
4 Correct 302 ms 101208 KB Output is correct
5 Correct 301 ms 101460 KB Output is correct
6 Correct 1 ms 5724 KB Output is correct
7 Correct 1 ms 5724 KB Output is correct
8 Correct 1 ms 5724 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Correct 1 ms 5724 KB Output is correct
3 Correct 1 ms 5720 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 9928 KB Output is correct
9 Correct 2 ms 9820 KB Output is correct
10 Correct 2 ms 9820 KB Output is correct
11 Correct 56 ms 10720 KB Output is correct
12 Correct 3 ms 10076 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 13944 KB Output is correct
2 Correct 195 ms 13912 KB Output is correct
3 Correct 277 ms 13944 KB Output is correct
4 Correct 257 ms 13944 KB Output is correct
5 Correct 249 ms 13916 KB Output is correct
6 Correct 1 ms 5724 KB Output is correct
7 Correct 1 ms 5724 KB Output is correct
8 Correct 2 ms 5724 KB Output is correct
9 Correct 980 ms 13972 KB Output is correct
10 Correct 2 ms 9820 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 105812 KB Output is correct
2 Correct 307 ms 106068 KB Output is correct
3 Correct 310 ms 106060 KB Output is correct
4 Correct 347 ms 106700 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 13940 KB Output is correct
2 Correct 193 ms 13948 KB Output is correct
3 Correct 259 ms 13948 KB Output is correct
4 Correct 252 ms 13948 KB Output is correct
5 Correct 251 ms 13916 KB Output is correct
6 Correct 296 ms 106220 KB Output is correct
7 Correct 307 ms 105808 KB Output is correct
8 Correct 309 ms 106068 KB Output is correct
9 Correct 338 ms 106832 KB Output is correct
10 Correct 291 ms 101464 KB Output is correct
11 Correct 293 ms 101200 KB Output is correct
12 Correct 329 ms 102736 KB Output is correct
13 Correct 326 ms 101204 KB Output is correct
14 Correct 287 ms 101300 KB Output is correct
15 Correct 1 ms 5724 KB Output is correct
16 Correct 2 ms 5724 KB Output is correct
17 Correct 1 ms 5724 KB Output is correct
18 Correct 2 ms 9816 KB Output is correct
19 Correct 2 ms 9820 KB Output is correct
20 Correct 2 ms 9820 KB Output is correct
21 Correct 2 ms 9820 KB Output is correct
22 Correct 2 ms 9820 KB Output is correct
23 Correct 2 ms 9820 KB Output is correct
24 Correct 2 ms 10072 KB Output is correct
25 Correct 69 ms 10776 KB Output is correct
26 Correct 2 ms 9820 KB Output is correct
27 Correct 973 ms 13952 KB Output is correct
28 Correct 2578 ms 106800 KB Output is correct
29 Correct 2516 ms 106124 KB Output is correct
30 Correct 2664 ms 105852 KB Output is correct
31 Correct 2564 ms 107456 KB Output is correct
32 Correct 2 ms 9820 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 13944 KB Output is correct
2 Correct 204 ms 13956 KB Output is correct
3 Correct 258 ms 14164 KB Output is correct
4 Correct 254 ms 13940 KB Output is correct
5 Correct 247 ms 13944 KB Output is correct
6 Correct 296 ms 106052 KB Output is correct
7 Correct 316 ms 105928 KB Output is correct
8 Correct 319 ms 106280 KB Output is correct
9 Correct 330 ms 106712 KB Output is correct
10 Correct 296 ms 101456 KB Output is correct
11 Correct 278 ms 101372 KB Output is correct
12 Correct 361 ms 102992 KB Output is correct
13 Correct 319 ms 101300 KB Output is correct
14 Correct 293 ms 101200 KB Output is correct
15 Correct 3064 ms 106484 KB Output is correct
16 Correct 11545 ms 107540 KB Output is correct
17 Correct 1 ms 5936 KB Output is correct
18 Correct 1 ms 5724 KB Output is correct
19 Correct 1 ms 5596 KB Output is correct
20 Correct 2 ms 9820 KB Output is correct
21 Correct 2 ms 9820 KB Output is correct
22 Correct 3 ms 9820 KB Output is correct
23 Correct 3 ms 9820 KB Output is correct
24 Correct 3 ms 9820 KB Output is correct
25 Correct 2 ms 9816 KB Output is correct
26 Correct 2 ms 9820 KB Output is correct
27 Correct 56 ms 10800 KB Output is correct
28 Correct 2 ms 9816 KB Output is correct
29 Correct 1036 ms 13956 KB Output is correct
30 Correct 2571 ms 106244 KB Output is correct
31 Correct 9572 ms 106656 KB Output is correct
32 Correct 9845 ms 106748 KB Output is correct
33 Correct 2574 ms 105884 KB Output is correct
34 Correct 9718 ms 106060 KB Output is correct
35 Correct 2687 ms 105820 KB Output is correct
36 Correct 9645 ms 106072 KB Output is correct
37 Correct 2498 ms 107504 KB Output is correct
38 Correct 9679 ms 107380 KB Output is correct
39 Correct 2 ms 9816 KB Output is correct
40 Correct 9918 ms 106108 KB Output is correct