oj.uz

답안 #202413

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
202413 2020-02-16T04:02:51 Z gs18115 웜뱃 (IOI13_wombats) C++14
55 / 100
 20000 ms 138980 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;
        for(int k=0;k<c;k++)
        {
            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;
        for(int k=0;k<c;k++)
        {
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 11384 KB Output is correct
2 Correct 12 ms 11384 KB Output is correct
3 Correct 97 ms 13052 KB Output is correct
4 Correct 16 ms 11384 KB Output is correct
5 Correct 13 ms 11384 KB Output is correct
6 Correct 6 ms 2680 KB Output is correct
7 Correct 6 ms 2680 KB Output is correct
8 Correct 6 ms 2680 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 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 7 ms 2808 KB Output is correct
5 Correct 8 ms 2808 KB Output is correct
6 Correct 8 ms 2812 KB Output is correct
7 Correct 8 ms 2808 KB Output is correct
8 Correct 7 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 96 ms 3964 KB Output is correct
12 Correct 8 ms 2812 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2704 ms 4512 KB Output is correct
2 Correct 3570 ms 4472 KB Output is correct
3 Correct 2770 ms 4472 KB Output is correct
4 Correct 2677 ms 4472 KB Output is correct
5 Correct 2698 ms 4472 KB Output is correct
6 Correct 6 ms 2680 KB Output is correct
7 Correct 6 ms 2680 KB Output is correct
8 Correct 6 ms 2680 KB Output is correct
9 Correct 17602 ms 4436 KB Output is correct
10 Correct 6 ms 2680 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 16248 KB Output is correct
2 Correct 20 ms 16248 KB Output is correct
3 Correct 20 ms 16248 KB Output is correct
4 Correct 64 ms 17016 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2742 ms 4324 KB Output is correct
2 Correct 3580 ms 4600 KB Output is correct
3 Correct 2799 ms 4600 KB Output is correct
4 Correct 2683 ms 4472 KB Output is correct
5 Correct 2723 ms 4472 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 62 ms 17144 KB Output is correct
10 Correct 12 ms 11384 KB Output is correct
11 Correct 13 ms 11384 KB Output is correct
12 Correct 97 ms 13048 KB Output is correct
13 Correct 12 ms 11388 KB Output is correct
14 Correct 13 ms 11384 KB Output is correct
15 Correct 7 ms 2680 KB Output is correct
16 Correct 6 ms 2680 KB Output is correct
17 Correct 7 ms 2680 KB Output is correct
18 Correct 8 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 99 ms 3832 KB Output is correct
26 Correct 8 ms 2808 KB Output is correct
27 Correct 17561 ms 4492 KB Output is correct
28 Execution timed out 20063 ms 100512 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2731 ms 4472 KB Output is correct
2 Correct 3647 ms 4472 KB Output is correct
3 Correct 2827 ms 4472 KB Output is correct
4 Correct 2690 ms 4344 KB Output is correct
5 Correct 2738 ms 4472 KB Output is correct
6 Correct 20 ms 16248 KB Output is correct
7 Correct 20 ms 16248 KB Output is correct
8 Correct 19 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 14 ms 11384 KB Output is correct
12 Correct 105 ms 13052 KB Output is correct
13 Correct 14 ms 11384 KB Output is correct
14 Correct 13 ms 11384 KB Output is correct
15 Execution timed out 20094 ms 138980 KB Time limit exceeded
16 Halted 0 ms 0 KB -