oj.uz

Submission #61199

# Submission time Handle Problem Language Result Execution time Memory
61199 2018-07-25T10:57:52 Z Vahan Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 12 ms 5484 KB 
#include "crocodile.h"
#include<vector>
#include<set>
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];
set<pair<int,int> > ss;
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;
        ss.insert(mp(0,P[i]));
    }
    for(int i=0;i<N;i++)
    {
        if(ss.empty())
            break;
        int v=ss.begin()->second;
        ss.erase(ss.begin());
        d[v]=er[v];
        er[v]=MAX;
        for(int j=0;j<g[v].size();j++)
        {
            int to=g[v][j].first;
            int dis=g[v][j].second;
            if(d[to]!=MAX)
                continue;
            if(ar[to]>=dis+d[v])
            {
                ss.erase(mp(er[to],to));
                er[to]=ar[to];
                ss.insert(mp(er[to],to));
                ar[to]=dis+d[v];
            }
            else if(er[to]>dis+d[v])
            {
                ss.erase(mp(er[to],to));
                er[to]=d[v]+dis;
                ss.insert(mp(er[to],to));
            }

        }
    }
    return d[0];
}

Compilation message

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

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Correct 8 ms 5124 KB Output is correct
3 Correct 8 ms 5296 KB Output is correct
4 Correct 8 ms 5312 KB Output is correct
5 Correct 9 ms 5372 KB Output is correct
6 Correct 8 ms 5372 KB Output is correct
7 Correct 9 ms 5372 KB Output is correct
8 Correct 11 ms 5372 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Correct 8 ms 5124 KB Output is correct
3 Correct 8 ms 5296 KB Output is correct
4 Correct 8 ms 5312 KB Output is correct
5 Correct 9 ms 5372 KB Output is correct
6 Correct 8 ms 5372 KB Output is correct
7 Correct 9 ms 5372 KB Output is correct
8 Correct 11 ms 5372 KB Output is correct
9 Incorrect 12 ms 5484 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Correct 8 ms 5124 KB Output is correct
3 Correct 8 ms 5296 KB Output is correct
4 Correct 8 ms 5312 KB Output is correct
5 Correct 9 ms 5372 KB Output is correct
6 Correct 8 ms 5372 KB Output is correct
7 Correct 9 ms 5372 KB Output is correct
8 Correct 11 ms 5372 KB Output is correct
9 Incorrect 12 ms 5484 KB Output isn't correct
10 Halted 0 ms 0 KB -