oj.uz

Submission #64943

# Submission time Handle Problem Language Result Execution time Memory
64943 2018-08-06T08:27:48 Z gs18115 None (KOI18_watertank) C++14
60 / 100
 3000 ms 190744 KB 
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL INF=1e18;
const LL SC=1002;
const LL MAXN=1005;
pair<pair<LL,LL>,LL>adj[MAXN][MAXN][5];
LL adjN[MAXN][MAXN];
LL dist[MAXN][MAXN];
bool inQ[MAXN][MAXN];
LL N,M,i,j,H,a,s;
void makeedge(LL i1,LL j1,LL i2,LL j2,LL w)
{
    adj[i1][j1][adjN[i1][j1]++]=make_pair(make_pair(i2,j2),w);
    adj[i2][j2][adjN[i2][j2]++]=make_pair(make_pair(i1,j1),w);
    return;
}
void spfa()
{
    queue<pair<LL,LL> >Q;
    LL i;
    for(i=0;i<MAXN;i++)
        fill(dist[i],dist[i]+MAXN,INF);
    for(i=0;i<MAXN;i++)
        fill(inQ[i],inQ[i]+MAXN,false);
    dist[SC][SC]=0;
    Q.push(make_pair(SC,SC));
    while(!Q.empty())
    {
        LL hi=Q.front().first;
        LL hj=Q.front().second;
        Q.pop();
        inQ[hi][hj]=false;
        for(i=0;i<adjN[hi][hj];i++)
        {
            LL ti=adj[hi][hj][i].first.first;
            LL tj=adj[hi][hj][i].first.second;
            LL wei=adj[hi][hj][i].second;
            if(dist[ti][tj]>max(wei,dist[hi][hj]))
            {
                dist[ti][tj]=max(wei,dist[hi][hj]);
                if(!inQ[ti][tj])
                {
                    inQ[ti][tj]=true;
                    Q.push(make_pair(ti,tj));
                }
            }
        }
    }
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>M>>H;
    for(i=0;i<=N;i++)
    {
        for(j=0;j<M;j++)
        {
            cin>>a;
            if(a==-1)
                continue;
            else if(i==0)
                makeedge(i,j,SC,SC,a);
            else if(i==N)
                makeedge(i-1,j,SC,SC,a);
            else
                makeedge(i,j,i-1,j,a);
        }
    }
    for(i=0;i<N;i++)
    {
        for(j=0;j<=M;j++)
        {
            cin>>a;
            if(a==-1)
                continue;
            else if(j==0)
                makeedge(i,j,SC,SC,a);
            else if(j==M)
                makeedge(i,j-1,SC,SC,a);
            else
                makeedge(i,j,i,j-1,a);
        }
    }
    spfa();
    for(i=0;i<N;i++)
        for(j=0;j<M;j++)
            s+=(dist[i][j]==INF?H:dist[i][j]);
    cout<<s<<endl;
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9208 KB Output is correct
2 Correct 11 ms 9444 KB Output is correct
3 Correct 14 ms 9444 KB Output is correct
4 Correct 12 ms 9444 KB Output is correct
5 Correct 10 ms 9444 KB Output is correct
6 Correct 11 ms 9448 KB Output is correct
7 Correct 11 ms 9664 KB Output is correct
8 Correct 10 ms 9664 KB Output is correct
9 Correct 10 ms 9724 KB Output is correct
10 Correct 12 ms 9724 KB Output is correct
11 Correct 10 ms 9724 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9724 KB Output is correct
2 Correct 10 ms 9724 KB Output is correct
3 Correct 14 ms 9724 KB Output is correct
4 Correct 12 ms 9756 KB Output is correct
5 Correct 9 ms 9756 KB Output is correct
6 Correct 10 ms 9756 KB Output is correct
7 Correct 9 ms 9784 KB Output is correct
8 Correct 10 ms 9784 KB Output is correct
9 Correct 11 ms 9784 KB Output is correct
10 Correct 9 ms 9784 KB Output is correct
11 Correct 10 ms 9784 KB Output is correct
12 Correct 13 ms 9784 KB Output is correct
13 Correct 10 ms 9864 KB Output is correct
14 Correct 10 ms 9864 KB Output is correct
15 Correct 9 ms 9864 KB Output is correct
16 Correct 11 ms 9864 KB Output is correct
17 Correct 12 ms 10016 KB Output is correct
18 Correct 11 ms 10016 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 10016 KB Output is correct
2 Correct 11 ms 10016 KB Output is correct
3 Correct 292 ms 123076 KB Output is correct
4 Correct 406 ms 136184 KB Output is correct
5 Correct 11 ms 136184 KB Output is correct
6 Correct 506 ms 150448 KB Output is correct
7 Correct 346 ms 150448 KB Output is correct
8 Correct 449 ms 159212 KB Output is correct
9 Correct 297 ms 159212 KB Output is correct
10 Correct 10 ms 159212 KB Output is correct
11 Correct 538 ms 159212 KB Output is correct
12 Correct 10 ms 159212 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 159212 KB Output is correct
2 Correct 10 ms 159212 KB Output is correct
3 Correct 12 ms 159212 KB Output is correct
4 Correct 12 ms 159212 KB Output is correct
5 Correct 10 ms 159212 KB Output is correct
6 Correct 10 ms 159212 KB Output is correct
7 Correct 14 ms 159212 KB Output is correct
8 Correct 14 ms 159212 KB Output is correct
9 Correct 15 ms 159212 KB Output is correct
10 Correct 15 ms 159212 KB Output is correct
11 Correct 12 ms 159212 KB Output is correct
12 Correct 11 ms 159212 KB Output is correct
13 Correct 13 ms 159212 KB Output is correct
14 Correct 10 ms 159212 KB Output is correct
15 Correct 12 ms 159212 KB Output is correct
16 Correct 12 ms 159212 KB Output is correct
17 Correct 11 ms 159212 KB Output is correct
18 Correct 14 ms 159212 KB Output is correct
19 Correct 14 ms 159212 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 159212 KB Output is correct
2 Correct 19 ms 159212 KB Output is correct
3 Correct 12 ms 159212 KB Output is correct
4 Correct 10 ms 159212 KB Output is correct
5 Correct 14 ms 159212 KB Output is correct
6 Correct 184 ms 159212 KB Output is correct
7 Correct 12 ms 159212 KB Output is correct
8 Correct 11 ms 159212 KB Output is correct
9 Correct 313 ms 159212 KB Output is correct
10 Correct 11 ms 159212 KB Output is correct
11 Correct 11 ms 159212 KB Output is correct
12 Correct 209 ms 159212 KB Output is correct
13 Correct 305 ms 159212 KB Output is correct
14 Correct 11 ms 159212 KB Output is correct
15 Correct 329 ms 164692 KB Output is correct
16 Correct 12 ms 164692 KB Output is correct
17 Correct 10 ms 164692 KB Output is correct
18 Correct 12 ms 164692 KB Output is correct
19 Correct 433 ms 172696 KB Output is correct
20 Correct 14 ms 172696 KB Output is correct
21 Execution timed out 3033 ms 190744 KB Time limit exceeded
22 Halted 0 ms 0 KB -