oj.uz

Submission #126635

# Submission time Handle Problem Language Result Execution time Memory
126635 2019-07-08T08:04:49 Z DodgeBallMan Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 685 ms 67176 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
#define pii pair<int, int>
#define x first
#define y second 

using namespace std;

const int N = 1e5 + 10;
int cnt[N];
vector<pii> g[N];
priority_queue< pii, vector<pii>, greater<pii> > q; 

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]].emplace_back( l[i], r[i][1] );
        g[r[i][1]].emplace_back( l[i], r[i][0] );
    }
    for( int i = 0 ; i < k ; i++ ) {
        cnt[p[i]]++;
        q.push( pii( 0, p[i] ) );
    }
    while( !q.empty() ) {
        pii te = q.top(); q.pop();
        //printf("%d %d\n",te.y,te.x);
        cnt[te.y]++;
        if( cnt[te.y] != 2 ) continue ;
        if( te.y == 0 ) return te.x;
        for( pii i : g[te.y] ) if( cnt[i.y] < 2 ) q.push( pii( i.x + te.x, i.y ) );
    }
}       

// int main() 
// {
//     int n, m, r[N][2], l[N], k, p[N];
//     scanf("%d %d",&n,&m);
//     for( int i = 0 ; i < m ; i++ ) scanf("%d %d",&r[i][0],&r[i][1]);
//     for( int i = 0 ; i < m ; i++ ) scanf("%d",&l[i]);
//     scanf("%d",&k);
//     for( int i = 0 ; i < k ; i++ ) scanf("%d",&p[i]);
//     printf("%d",travel_plan( n, m, r, l, k, p ) );
//     return 0;
// }

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:32:1: warning: control reaches end of non-void function [-Wreturn-type]
 }       
 ^

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2708 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 5 ms 2760 KB Output is correct
8 Correct 5 ms 2808 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 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2708 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 5 ms 2760 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 6 ms 3064 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 5 ms 2856 KB Output is correct
12 Correct 10 ms 3320 KB Output is correct
13 Correct 9 ms 3244 KB Output is correct
14 Correct 5 ms 2756 KB Output is correct
15 Correct 5 ms 2808 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 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2708 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 5 ms 2760 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 6 ms 3064 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 5 ms 2856 KB Output is correct
12 Correct 10 ms 3320 KB Output is correct
13 Correct 9 ms 3244 KB Output is correct
14 Correct 5 ms 2756 KB Output is correct
15 Correct 5 ms 2808 KB Output is correct
16 Correct 633 ms 64332 KB Output is correct
17 Correct 100 ms 13460 KB Output is correct
18 Correct 113 ms 14860 KB Output is correct
19 Correct 685 ms 67176 KB Output is correct
20 Correct 341 ms 49612 KB Output is correct
21 Correct 51 ms 7672 KB Output is correct
22 Correct 505 ms 46328 KB Output is correct