oj.uz

Submission #870802

# Submission time Handle Problem Language Result Execution time Memory
870802 2023-11-09T07:17:06 Z HuyQuang_re_Zero Wombats (IOI13_wombats) C++14
100 / 100
 8304 ms 197900 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<=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

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 290 ms 181840 KB Output is correct
2 Correct 265 ms 182120 KB Output is correct
3 Correct 312 ms 184576 KB Output is correct
4 Correct 276 ms 181844 KB Output is correct
5 Correct 256 ms 181844 KB Output is correct
6 Correct 2 ms 5724 KB Output is correct
7 Correct 1 ms 5824 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 1 ms 5724 KB Output is correct
2 Correct 1 ms 5724 KB Output is correct
3 Correct 1 ms 5724 KB Output is correct
4 Correct 3 ms 12380 KB Output is correct
5 Correct 3 ms 12632 KB Output is correct
6 Correct 3 ms 12380 KB Output is correct
7 Correct 3 ms 12380 KB Output is correct
8 Correct 3 ms 12380 KB Output is correct
9 Correct 3 ms 12380 KB Output is correct
10 Correct 3 ms 12380 KB Output is correct
11 Correct 57 ms 13396 KB Output is correct
12 Correct 3 ms 12380 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 13912 KB Output is correct
2 Correct 196 ms 13956 KB Output is correct
3 Correct 256 ms 13916 KB Output is correct
4 Correct 249 ms 13912 KB Output is correct
5 Correct 250 ms 13948 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
9 Correct 970 ms 13968 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 272 ms 186708 KB Output is correct
2 Correct 268 ms 186808 KB Output is correct
3 Correct 285 ms 186708 KB Output is correct
4 Correct 290 ms 187984 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 13948 KB Output is correct
2 Correct 195 ms 13956 KB Output is correct
3 Correct 255 ms 13952 KB Output is correct
4 Correct 248 ms 13968 KB Output is correct
5 Correct 244 ms 13916 KB Output is correct
6 Correct 268 ms 186804 KB Output is correct
7 Correct 260 ms 186708 KB Output is correct
8 Correct 284 ms 186788 KB Output is correct
9 Correct 296 ms 188100 KB Output is correct
10 Correct 259 ms 182056 KB Output is correct
11 Correct 265 ms 182100 KB Output is correct
12 Correct 316 ms 184764 KB Output is correct
13 Correct 278 ms 182064 KB Output is correct
14 Correct 254 ms 181844 KB Output is correct
15 Correct 1 ms 5724 KB Output is correct
16 Correct 1 ms 5724 KB Output is correct
17 Correct 1 ms 5724 KB Output is correct
18 Correct 3 ms 12380 KB Output is correct
19 Correct 3 ms 12636 KB Output is correct
20 Correct 3 ms 12624 KB Output is correct
21 Correct 3 ms 12632 KB Output is correct
22 Correct 3 ms 12380 KB Output is correct
23 Correct 3 ms 12636 KB Output is correct
24 Correct 4 ms 12636 KB Output is correct
25 Correct 58 ms 14928 KB Output is correct
26 Correct 3 ms 12632 KB Output is correct
27 Correct 962 ms 14020 KB Output is correct
28 Correct 1907 ms 191060 KB Output is correct
29 Correct 1965 ms 190124 KB Output is correct
30 Correct 1999 ms 190528 KB Output is correct
31 Correct 1897 ms 192476 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 244 ms 14212 KB Output is correct
2 Correct 193 ms 13964 KB Output is correct
3 Correct 250 ms 13912 KB Output is correct
4 Correct 251 ms 13912 KB Output is correct
5 Correct 251 ms 14168 KB Output is correct
6 Correct 284 ms 186792 KB Output is correct
7 Correct 280 ms 186708 KB Output is correct
8 Correct 279 ms 186684 KB Output is correct
9 Correct 289 ms 187980 KB Output is correct
10 Correct 258 ms 182056 KB Output is correct
11 Correct 264 ms 182096 KB Output is correct
12 Correct 314 ms 184716 KB Output is correct
13 Correct 276 ms 182068 KB Output is correct
14 Correct 265 ms 181944 KB Output is correct
15 Correct 2892 ms 196936 KB Output is correct
16 Correct 8304 ms 197900 KB Output is correct
17 Correct 2 ms 5724 KB Output is correct
18 Correct 1 ms 5724 KB Output is correct
19 Correct 1 ms 5724 KB Output is correct
20 Correct 3 ms 12380 KB Output is correct
21 Correct 3 ms 12636 KB Output is correct
22 Correct 3 ms 12380 KB Output is correct
23 Correct 3 ms 12380 KB Output is correct
24 Correct 3 ms 12636 KB Output is correct
25 Correct 3 ms 12636 KB Output is correct
26 Correct 3 ms 12636 KB Output is correct
27 Correct 57 ms 14800 KB Output is correct
28 Correct 3 ms 12636 KB Output is correct
29 Correct 961 ms 14272 KB Output is correct
30 Correct 1914 ms 191200 KB Output is correct
31 Correct 7117 ms 195492 KB Output is correct
32 Correct 7135 ms 194960 KB Output is correct
33 Correct 1969 ms 190288 KB Output is correct
34 Correct 7229 ms 193996 KB Output is correct
35 Correct 2021 ms 189776 KB Output is correct
36 Correct 7309 ms 193732 KB Output is correct
37 Correct 1880 ms 192960 KB Output is correct
38 Correct 7046 ms 195564 KB Output is correct
39 Correct 2 ms 9820 KB Output is correct
40 Correct 7636 ms 194140 KB Output is correct