oj.uz

Submission #29500

# Submission time Handle Problem Language Result Execution time Memory
29500 2017-07-19T14:07:13 Z Nikefor Crocodile's Underground City (IOI11_crocodile) C++
100 / 100
 943 ms 161776 KB 
#include "crocodile.h"
#include<bits/stdc++.h>
#define ii pair<int,int>
using namespace std;
int visit[100002];
int res;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    priority_queue<ii, vector<ii>, greater<ii> > q;
    vector<ii> adj[N+2];
    for(int i=0; i<M; i++) {
        int v1 = R[i][0], v2 = R[i][1];
        adj[v1].push_back(make_pair(v2,i));
        adj[v2].push_back(make_pair(v1,i));
    }
    for(int i=0; i<K; i++) { q.push(make_pair(0,P[i])); visit[P[i]]++; }
    while(!q.empty()) {
         ii e = q.top();
         int v = e.second;
     //    printf("%d deyim\n", v);
         q.pop();

         visit[v]++;\
         if(visit[v]!=2) continue;
        if(!v){
            res = e.first;
            break;
        }
        for(int i=0; i<adj[v].size(); i++) {
            if(visit[adj[v][i].first]<2) q.push(make_pair(e.first+L[adj[v][i].second], adj[v][i].first ));
        }

    }
  return res;
}

Compilation message

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

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 119796 KB Output is correct
2 Correct 0 ms 119796 KB Output is correct
3 Correct 0 ms 119796 KB Output is correct
4 Correct 0 ms 119928 KB Output is correct
5 Correct 0 ms 119932 KB Output is correct
6 Correct 0 ms 119796 KB Output is correct
7 Correct 0 ms 119928 KB Output is correct
8 Correct 0 ms 119796 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 120072 KB Output is correct
2 Correct 0 ms 119796 KB Output is correct
3 Correct 0 ms 119928 KB Output is correct
4 Correct 6 ms 120224 KB Output is correct
5 Correct 3 ms 120060 KB Output is correct
6 Correct 0 ms 119796 KB Output is correct
7 Correct 0 ms 119928 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 883 ms 158016 KB Output is correct
2 Correct 129 ms 126764 KB Output is correct
3 Correct 146 ms 127952 KB Output is correct
4 Correct 943 ms 161776 KB Output is correct
5 Correct 419 ms 142684 KB Output is correct
6 Correct 56 ms 122752 KB Output is correct
7 Correct 593 ms 139124 KB Output is correct