oj.uz

Submission #202414

# Submission time Handle Problem Language Result Execution time Memory
202414 2020-02-16T04:04:16 Z gs18115 Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 189416 KB 
#include"wombats.h"
#include<iostream>
#include<vector>
#include<queue>
#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(int n,int l,int r)
{
    node&m=tr[n];
    node&x=tr[l];
    node&y=tr[r];
    for(int i=0;i<c;i++)
        for(int j=0;j<c;j++)
            opt[i][j]=-1;
    for(int i=0;i<c;i++)
    {
        int j=0;
        int&o=opt[i][j]=0;
        for(int k=0;++k<c;)
            if(x.d[i][k]+y.d[k][j]<x.d[i][o]+y.d[o][j])
                o=k;
    }
    for(int j=0;j<c;j++)
    {
        int i=c-1;
        int&o=opt[i][j]=0;
        for(int k=0;++k<c;)
            if(x.d[i][k]+y.d[k][j]<x.d[i][o]+y.d[o][j])
                o=k;
    }
    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];
            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;
        }
    }
    for(int i=0;i<c;i++)
        for(int j=0;j<c;j++)
            m.d[i][j]=x.d[i][opt[i][j]]+y.d[opt[i][j]][j];
    return;
}
int dn;
vector<pi>adj[100010];
int d[100010];
inline void dijk(int s)
{
    fill(d,d+dn,inf);
    priority_queue<pi,vector<pi>,greater<pi> >pq;
    pq.ep(d[s]=0,s);
    while(!pq.empty())
    {
        int x=pq.top().se;
        int cd=pq.top().fi;
        pq.pop();
        if(d[x]!=cd)
            continue;
        for(pi&t:adj[x])
            if(d[t.fi]>cd+t.se)
                pq.ep(d[t.fi]=cd+t.se,t.fi);
    }
    return;
}
vector<vector<int> >h,v;
inline void init(int n,int s,int e)
{
    node&x=tr[n];
    dn=(e-s+1)*c;
    for(int i=0;i<dn;i++)
        adj[i].clear();
    for(int i=s;i<=e;i++)
    {
        for(int j=0;j<c-1;j++)
        {
            int cn=i*c-s*c+j;
            adj[cn].eb(cn+1,h[i][j]);
            adj[cn+1].eb(cn,h[i][j]);
        }
    }
    for(int i=s;i<e;i++)
    {
        for(int j=0;j<c;j++)
        {
            int cn=i*c-s*c+j;
            adj[cn].eb(cn+c,v[i][j]);
        }
    }
    for(int i=0;i<c;i++)
    {
        dijk(i);
        for(int j=0;j<c;j++)
            x.d[i][j]=d[j+(e-s)*c];
    }
    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(cur,x.l,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(n,x.l,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(n,x.l,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 12 ms 11384 KB Output is correct
2 Correct 14 ms 11384 KB Output is correct
3 Correct 103 ms 13116 KB Output is correct
4 Correct 13 ms 11384 KB Output is correct
5 Correct 14 ms 11384 KB Output is correct
6 Correct 6 ms 2680 KB Output is correct
7 Correct 7 ms 2680 KB Output is correct
8 Correct 7 ms 2680 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2680 KB Output is correct
3 Correct 6 ms 2680 KB Output is correct
4 Correct 8 ms 2812 KB Output is correct
5 Correct 8 ms 2812 KB Output is correct
6 Correct 8 ms 2808 KB Output is correct
7 Correct 8 ms 2812 KB Output is correct
8 Correct 8 ms 2808 KB Output is correct
9 Correct 7 ms 2808 KB Output is correct
10 Correct 7 ms 2808 KB Output is correct
11 Correct 117 ms 3832 KB Output is correct
12 Correct 9 ms 2808 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1495 ms 4396 KB Output is correct
2 Correct 2511 ms 4404 KB Output is correct
3 Correct 1559 ms 4396 KB Output is correct
4 Correct 1481 ms 4428 KB Output is correct
5 Correct 1544 ms 4560 KB Output is correct
6 Correct 6 ms 2684 KB Output is correct
7 Correct 6 ms 2680 KB Output is correct
8 Correct 5 ms 2680 KB Output is correct
9 Correct 12024 ms 4428 KB Output is correct
10 Correct 7 ms 2680 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 16284 KB Output is correct
2 Correct 19 ms 16248 KB Output is correct
3 Correct 25 ms 16248 KB Output is correct
4 Correct 64 ms 17016 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1500 ms 4448 KB Output is correct
2 Correct 2526 ms 4472 KB Output is correct
3 Correct 1565 ms 4476 KB Output is correct
4 Correct 1488 ms 4472 KB Output is correct
5 Correct 1540 ms 4476 KB Output is correct
6 Correct 19 ms 16252 KB Output is correct
7 Correct 20 ms 16248 KB Output is correct
8 Correct 21 ms 16248 KB Output is correct
9 Correct 64 ms 17016 KB Output is correct
10 Correct 13 ms 11384 KB Output is correct
11 Correct 12 ms 11384 KB Output is correct
12 Correct 104 ms 13048 KB Output is correct
13 Correct 12 ms 11384 KB Output is correct
14 Correct 12 ms 11384 KB Output is correct
15 Correct 6 ms 2680 KB Output is correct
16 Correct 6 ms 2680 KB Output is correct
17 Correct 6 ms 2680 KB Output is correct
18 Correct 7 ms 2808 KB Output is correct
19 Correct 7 ms 2808 KB Output is correct
20 Correct 7 ms 2808 KB Output is correct
21 Correct 8 ms 2808 KB Output is correct
22 Correct 7 ms 2808 KB Output is correct
23 Correct 7 ms 2808 KB Output is correct
24 Correct 7 ms 2808 KB Output is correct
25 Correct 105 ms 3832 KB Output is correct
26 Correct 8 ms 2808 KB Output is correct
27 Correct 12032 ms 4472 KB Output is correct
28 Correct 18248 ms 100524 KB Output is correct
29 Correct 9110 ms 101532 KB Output is correct
30 Correct 8505 ms 101472 KB Output is correct
31 Execution timed out 20063 ms 105352 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1487 ms 4516 KB Output is correct
2 Correct 2485 ms 4472 KB Output is correct
3 Correct 1558 ms 4472 KB Output is correct
4 Correct 1459 ms 4396 KB Output is correct
5 Correct 1511 ms 4476 KB Output is correct
6 Correct 20 ms 16248 KB Output is correct
7 Correct 20 ms 16248 KB Output is correct
8 Correct 20 ms 16248 KB Output is correct
9 Correct 65 ms 17144 KB Output is correct
10 Correct 13 ms 11384 KB Output is correct
11 Correct 13 ms 11384 KB Output is correct
12 Correct 98 ms 13048 KB Output is correct
13 Correct 13 ms 11384 KB Output is correct
14 Correct 13 ms 11384 KB Output is correct
15 Correct 11892 ms 181300 KB Output is correct
16 Execution timed out 20032 ms 189416 KB Time limit exceeded
17 Halted 0 ms 0 KB -