oj.uz

Submission #202423

# Submission time Handle Problem Language Result Execution time Memory
202423 2020-02-16T04:29:14 Z gs18115 Wombats (IOI13_wombats) C++14
100 / 100
 9779 ms 188596 KB 
#include"wombats.h"
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
struct node
{
    int l,r;
    int d[200][200];
}tr[1500];
int r,c;
int opt[200][200];
inline void merge(node&m,node&x,node&y)
{
    for(int i=0;i<c;i++)
        for(int j=0;j<c;j++)
            opt[i][j]=-1;
    int&o0=opt[0][0]=0;
    m.d[0][0]=x.d[0][o0]+y.d[0][o0];
    for(int k=0;++k<c;)
        if(x.d[0][k]+y.d[k][0]<x.d[0][o0]+y.d[o0][0])
            o0=k,m.d[0][0]=x.d[0][o0]+y.d[o0][0];
    for(int i=1;i<c;i++)
    {
        int j=0;
        int&o=opt[i][j]=opt[i-1][j];
        m.d[i][j]=x.d[i][o]+y.d[o][j];
        for(int k=o;++k<c;)
            if(x.d[i][k]+y.d[k][j]<x.d[i][o]+y.d[o][j])
                o=k,m.d[i][j]=x.d[i][o]+y.d[o][j];
    }
    for(int j=1;j<c;j++)
    {
        int i=c-1;
        int&o=opt[i][j]=opt[i][j-1];
        m.d[i][j]=x.d[i][o]+y.d[o][j];
        for(int k=o;++k<c;)
            if(x.d[i][k]+y.d[k][j]<x.d[i][o]+y.d[o][j])
                o=k,m.d[i][j]=x.d[i][o]+y.d[o][j];
    }
    for(int l=-c;++l<c;)
    {
        for(int i=0;i<c;i++)
        {
            int j=i+l;
            if(j<0||j>=c||opt[i][j]!=-1)
                continue;
            int&o=opt[i][j]=opt[i][j-1];
            m.d[i][j]=x.d[i][o]+y.d[o][j];
            for(int k=o;++k<=opt[i+1][j];)
                if(x.d[i][k]+y.d[k][j]<x.d[i][o]+y.d[o][j])
                    o=k,m.d[i][j]=x.d[i][o]+y.d[o][j];
        }
    }
    return;
}
vector<vector<int> >h,v;
inline void init(int n,int s,int e)
{
    node&x=tr[n];
    node t,p;
    vector<int>ps(c,0);
        for(int i=1;i<c;i++)
            ps[i]=ps[i-1]+h[s][i-1];
    for(int i=0;i<c;i++)
        for(int j=0;j<c;j++)
            x.d[i][j]=i>j?ps[i]-ps[j]:ps[j]-ps[i];
    for(int r=s;r<e;r++)
    {
        p=x;
        for(int i=0;i<c;i++)
            for(int j=0;j<c;j++)
                p.d[i][j]+=v[r][j];
        for(int i=1;i<c;i++)
            ps[i]=ps[i-1]+h[r+1][i-1];
        for(int i=0;i<c;i++)
            for(int j=0;j<c;j++)
                t.d[i][j]=i>j?ps[i]-ps[j]:ps[j]-ps[i];
        merge(x,p,t);
    }
    return;
}
int tct=0,rt;
int init(int s,int e)
{
    int cur=tct++;
    node&x=tr[cur];
    if(e-s<15)
    {
        x.l=x.r=0;
        init(cur,s,e);
        return cur;
    }
    int m=(s+e)/2;
    x.l=init(s,m);
    x.r=init(m,e);
    merge(x,tr[x.l],tr[x.r]);
    return cur;
}
void ch(int n,int s,int e,int r)
{
    if(s>r||e<r)
        return;
    node&x=tr[n];
    if(e-s<15)
    {
        init(n,s,e);
        return;
    }
    int m=(s+e)/2;
    ch(x.l,s,m,r);
    ch(x.r,m,e,r);
    merge(x,tr[x.l],tr[x.r]);
    return;
}
void cv(int n,int s,int e,int r)
{
    if(s>r||e<=r)
        return;
    node&x=tr[n];
    if(e-s<15)
    {
        init(n,s,e);
        return;
    }
    int m=(s+e)/2;
    cv(x.l,s,m,r);
    cv(x.r,m,e,r);
    merge(x,tr[x.l],tr[x.r]);
    return;
}
void init(int R,int C,int H[5000][200],int V[5000][200])
{
    r=R;
    c=C;
    h.resize(r);
    for(int i=0;i<r;i++)
        for(int j=0;j<c-1;j++)
            h[i].eb(H[i][j]);
    v.resize(r-1);
    for(int i=0;i<r-1;i++)
        for(int j=0;j<c;j++)
            v[i].eb(V[i][j]);
    rt=init(0,r-1);
    return;
}
void changeH(int P,int Q,int W)
{
    h[P][Q]=W;
    ch(rt,0,r-1,P);
    return;
}
void changeV(int P,int Q,int W)
{
    v[P][Q]=W;
    cv(rt,0,r-1,P);
    return;
}
int escape(int V1,int V2)
{
    return tr[rt].d[V1][V2];
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 9208 KB Output is correct
2 Correct 145 ms 9320 KB Output is correct
3 Correct 220 ms 10872 KB Output is correct
4 Correct 133 ms 9208 KB Output is correct
5 Correct 140 ms 9308 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 5 ms 504 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 632 KB Output is correct
5 Correct 6 ms 632 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 6 ms 636 KB Output is correct
8 Correct 6 ms 632 KB Output is correct
9 Correct 6 ms 632 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 99 ms 1656 KB Output is correct
12 Correct 6 ms 632 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 2296 KB Output is correct
2 Correct 226 ms 2168 KB Output is correct
3 Correct 311 ms 2172 KB Output is correct
4 Correct 299 ms 2296 KB Output is correct
5 Correct 300 ms 2168 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 1054 ms 2296 KB Output is correct
10 Correct 5 ms 504 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 14072 KB Output is correct
2 Correct 142 ms 14072 KB Output is correct
3 Correct 137 ms 14072 KB Output is correct
4 Correct 186 ms 14968 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 2296 KB Output is correct
2 Correct 231 ms 2296 KB Output is correct
3 Correct 310 ms 2296 KB Output is correct
4 Correct 289 ms 2296 KB Output is correct
5 Correct 299 ms 2428 KB Output is correct
6 Correct 134 ms 14072 KB Output is correct
7 Correct 135 ms 14072 KB Output is correct
8 Correct 141 ms 14072 KB Output is correct
9 Correct 190 ms 14840 KB Output is correct
10 Correct 137 ms 9208 KB Output is correct
11 Correct 139 ms 9208 KB Output is correct
12 Correct 221 ms 10872 KB Output is correct
13 Correct 134 ms 9208 KB Output is correct
14 Correct 132 ms 9208 KB Output is correct
15 Correct 5 ms 504 KB Output is correct
16 Correct 5 ms 504 KB Output is correct
17 Correct 5 ms 504 KB Output is correct
18 Correct 6 ms 632 KB Output is correct
19 Correct 7 ms 632 KB Output is correct
20 Correct 6 ms 632 KB Output is correct
21 Correct 5 ms 632 KB Output is correct
22 Correct 6 ms 632 KB Output is correct
23 Correct 6 ms 632 KB Output is correct
24 Correct 6 ms 636 KB Output is correct
25 Correct 96 ms 1656 KB Output is correct
26 Correct 5 ms 632 KB Output is correct
27 Correct 1026 ms 2172 KB Output is correct
28 Correct 2157 ms 98296 KB Output is correct
29 Correct 2366 ms 97024 KB Output is correct
30 Correct 2353 ms 96760 KB Output is correct
31 Correct 2129 ms 100644 KB Output is correct
32 Correct 5 ms 504 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 2232 KB Output is correct
2 Correct 228 ms 2168 KB Output is correct
3 Correct 308 ms 2168 KB Output is correct
4 Correct 295 ms 2296 KB Output is correct
5 Correct 302 ms 2180 KB Output is correct
6 Correct 139 ms 14072 KB Output is correct
7 Correct 145 ms 14256 KB Output is correct
8 Correct 136 ms 14072 KB Output is correct
9 Correct 184 ms 14840 KB Output is correct
10 Correct 134 ms 9208 KB Output is correct
11 Correct 133 ms 9208 KB Output is correct
12 Correct 213 ms 10872 KB Output is correct
13 Correct 132 ms 9208 KB Output is correct
14 Correct 134 ms 9208 KB Output is correct
15 Correct 3578 ms 179316 KB Output is correct
16 Correct 9779 ms 183416 KB Output is correct
17 Correct 5 ms 504 KB Output is correct
18 Correct 5 ms 504 KB Output is correct
19 Correct 5 ms 504 KB Output is correct
20 Correct 6 ms 632 KB Output is correct
21 Correct 6 ms 632 KB Output is correct
22 Correct 6 ms 632 KB Output is correct
23 Correct 6 ms 632 KB Output is correct
24 Correct 6 ms 760 KB Output is correct
25 Correct 6 ms 632 KB Output is correct
26 Correct 6 ms 632 KB Output is correct
27 Correct 106 ms 3064 KB Output is correct
28 Correct 6 ms 632 KB Output is correct
29 Correct 1167 ms 2280 KB Output is correct
30 Correct 2240 ms 101992 KB Output is correct
31 Correct 7313 ms 187656 KB Output is correct
32 Correct 7363 ms 187912 KB Output is correct
33 Correct 2350 ms 99868 KB Output is correct
34 Correct 8141 ms 184192 KB Output is correct
35 Correct 2351 ms 99448 KB Output is correct
36 Correct 8141 ms 184116 KB Output is correct
37 Correct 2127 ms 103928 KB Output is correct
38 Correct 7689 ms 188596 KB Output is correct
39 Correct 5 ms 504 KB Output is correct
40 Correct 8450 ms 184236 KB Output is correct