oj.uz

Submission #62879

# Submission time Handle Problem Language Result Execution time Memory
62879 2018-07-30T15:41:29 Z theknife2001 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 1449 ms 67128 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
#define ll long long
#define ii pair< ll , int >
#define se second
#define fi first


using namespace std;
const int NN=1e5+55;
vector < pair < int , int > > vec[NN];
priority_queue < ii , vector <ii> , greater<ii> >pq;
ll dist[NN];
int cnt[NN];
int n;

void dijk()
{
    int v,u;
    long long l,c;
    while(pq.size())
    {
        c=pq.top().fi;
        u=pq.top().se;
        pq.pop();
        cnt[u]++;
        if(cnt[u]!=2)
            continue ;
        dist[u]=c;
        for(int i=0;i<vec[u].size();i++)
        {
            l=vec[u][i].fi;
            v=vec[u][i].se;
            if(cnt[v]<2)
                pq.push({l+c,v});
        }
    }
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    n=N;
    for(int i=0;i<N;i++)
        dist[i]=1e17;
    for(int i=0;i<K;i++)
    {
        dist[P[i]]=0;
        pq.push({0,P[i]});
        cnt[P[i]]=1;
    }
    for(int i=0;i<M;i++)
    {
        vec[R[i][0]].push_back({L[i],R[i][1]});
        vec[R[i][1]].push_back({L[i],R[i][0]});
    }
    dijk();
    int ret=dist[0];
    return ret;
}

Compilation message

crocodile.cpp: In function 'void dijk()':
crocodile.cpp:30:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<vec[u].size();i++)
                     ~^~~~~~~~~~~~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 6 ms 2792 KB Output is correct
3 Correct 3 ms 2872 KB Output is correct
4 Correct 7 ms 2932 KB Output is correct
5 Correct 6 ms 2932 KB Output is correct
6 Correct 5 ms 2996 KB Output is correct
7 Correct 8 ms 3060 KB Output is correct
8 Correct 5 ms 3076 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 6 ms 2792 KB Output is correct
3 Correct 3 ms 2872 KB Output is correct
4 Correct 7 ms 2932 KB Output is correct
5 Correct 6 ms 2932 KB Output is correct
6 Correct 5 ms 2996 KB Output is correct
7 Correct 8 ms 3060 KB Output is correct
8 Correct 5 ms 3076 KB Output is correct
9 Correct 8 ms 3476 KB Output is correct
10 Correct 6 ms 3476 KB Output is correct
11 Correct 6 ms 3476 KB Output is correct
12 Correct 13 ms 4148 KB Output is correct
13 Correct 13 ms 4148 KB Output is correct
14 Correct 5 ms 4148 KB Output is correct
15 Correct 7 ms 4148 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 6 ms 2792 KB Output is correct
3 Correct 3 ms 2872 KB Output is correct
4 Correct 7 ms 2932 KB Output is correct
5 Correct 6 ms 2932 KB Output is correct
6 Correct 5 ms 2996 KB Output is correct
7 Correct 8 ms 3060 KB Output is correct
8 Correct 5 ms 3076 KB Output is correct
9 Correct 8 ms 3476 KB Output is correct
10 Correct 6 ms 3476 KB Output is correct
11 Correct 6 ms 3476 KB Output is correct
12 Correct 13 ms 4148 KB Output is correct
13 Correct 13 ms 4148 KB Output is correct
14 Correct 5 ms 4148 KB Output is correct
15 Correct 7 ms 4148 KB Output is correct
16 Correct 1304 ms 64080 KB Output is correct
17 Correct 136 ms 64080 KB Output is correct
18 Correct 167 ms 64080 KB Output is correct
19 Correct 1449 ms 67128 KB Output is correct
20 Correct 906 ms 67128 KB Output is correct
21 Correct 86 ms 67128 KB Output is correct
22 Correct 795 ms 67128 KB Output is correct