oj.uz

Submission #61193

# Submission time Handle Problem Language Result Execution time Memory
61193 2018-07-25T10:36:54 Z Vahan Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 13 ms 5716 KB 
#include "crocodile.h"
#include<vector>
using namespace std;
#define mp make_pair
const long long MAX=100000000000000000;
long long d[200000],er[200000],ar[200000];
vector<pair<int,int> > g[200000];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    for(int i=0;i<M;i++)
    {
        g[R[i][0]].push_back(mp(R[i][1],L[i]));
        g[R[i][1]].push_back(mp(R[i][0],L[i]));
    }
    for(int i=0;i<N;i++)
    {
        ar[i]=MAX;
        er[i]=MAX;
        d[i]=MAX;
    }
    for(int i=0;i<K;i++)
        er[P[i]]=0;
    for(int i=0;i<N;i++)
    {
        int v=-1;
        for(int j=0;j<N;j++)
            if(d[j]==MAX && (v==-1 || er[j]<er[v]))
                v=j;
        if(v==-1)
            break;
        d[v]=er[v];
        er[v]=MAX;
        for(int i=0;i<g[v].size();i++)
        {
            int to=g[v][i].first;
            int dis=g[v][i].second;
            if(d[to]!=MAX)
                continue;
            if(ar[to]>=dis+d[v])
            {
                er[to]=ar[to];
                ar[to]=dis+d[v];
            }
            else if(er[to]>dis+d[v])
                er[to]=d[v]+dis;
        }
    }
    return d[0];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:33:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<g[v].size();i++)
                     ~^~~~~~~~~~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 9 ms 5196 KB Output is correct
4 Correct 11 ms 5332 KB Output is correct
5 Correct 13 ms 5360 KB Output is correct
6 Correct 8 ms 5548 KB Output is correct
7 Correct 12 ms 5560 KB Output is correct
8 Correct 11 ms 5572 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 9 ms 5196 KB Output is correct
4 Correct 11 ms 5332 KB Output is correct
5 Correct 13 ms 5360 KB Output is correct
6 Correct 8 ms 5548 KB Output is correct
7 Correct 12 ms 5560 KB Output is correct
8 Correct 11 ms 5572 KB Output is correct
9 Incorrect 10 ms 5716 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5112 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 9 ms 5196 KB Output is correct
4 Correct 11 ms 5332 KB Output is correct
5 Correct 13 ms 5360 KB Output is correct
6 Correct 8 ms 5548 KB Output is correct
7 Correct 12 ms 5560 KB Output is correct
8 Correct 11 ms 5572 KB Output is correct
9 Incorrect 10 ms 5716 KB Output isn't correct
10 Halted 0 ms 0 KB -