oj.uz

Submission #848389

# Submission time Handle Problem Language Result Execution time Memory
848389 2023-09-12T10:55:25 Z Warinchai Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 415 ms 91924 KB 
#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,long long> >v[100005];
pair<long long,long long> dis[100005];
bool vis[100005];
priority_queue<pair<long long,int>,vector<pair<long long,int> >, greater<pair<long long,int> > >pq;
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
    for(int i=0;i<m;i++){
        int st=r[i][0];
        int en=r[i][1];
        int w=l[i];
        v[st].push_back({en,w});
        v[en].push_back({st,w});
    }
    for(int i=0;i<n;i++){
        dis[i].first=dis[i].second=LLONG_MAX;
    }
    for(int i=0;i<k;i++){
        dis[p[i]].first=dis[p[i]].second=0;
        pq.push({0,p[i]});
    }
    while(!pq.empty()){
        int x=pq.top().second;
        long long cost=pq.top().first;
        pq.pop();
        if(vis[x]){
            continue;
        }
        vis[x]=1;
        for(int i=0;i<v[x].size();i++){
            int nn=v[x][i].first;
            long long nc=cost+v[x][i].second;
            if(nc<dis[nn].second){
                dis[nn].second=nc;
                if(dis[nn].second<dis[nn].first)swap(dis[nn].second,dis[nn].first);
                if(dis[nn].second!=LLONG_MAX){
                    pq.push({dis[nn].second,nn});
                }
            }
        }
    }
    return dis[0].second;
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for(int i=0;i<v[x].size();i++){
      |                     ~^~~~~~~~~~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 2 ms 6488 KB Output is correct
5 Correct 2 ms 6488 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 2 ms 6488 KB Output is correct
5 Correct 2 ms 6488 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 3 ms 6744 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 3 ms 7004 KB Output is correct
13 Correct 3 ms 7256 KB Output is correct
14 Correct 1 ms 6488 KB Output is correct
15 Correct 2 ms 6488 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 2 ms 6488 KB Output is correct
5 Correct 2 ms 6488 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 3 ms 6744 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 3 ms 7004 KB Output is correct
13 Correct 3 ms 7256 KB Output is correct
14 Correct 1 ms 6488 KB Output is correct
15 Correct 2 ms 6488 KB Output is correct
16 Correct 334 ms 84756 KB Output is correct
17 Correct 53 ms 19864 KB Output is correct
18 Correct 65 ms 22096 KB Output is correct
19 Correct 415 ms 91924 KB Output is correct
20 Correct 226 ms 70464 KB Output is correct
21 Correct 26 ms 14160 KB Output is correct
22 Correct 226 ms 67392 KB Output is correct