oj.uz

Submission #29120

# Submission time Handle Problem Language Result Execution time Memory
29120 2017-07-18T10:15:54 Z osmanorhan Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 793 ms 176712 KB 
#include "crocodile.h"
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <list>
#include <climits>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cassert>
#include <vector>
#define all(x) x.begin() , x.end()
#define fi first
#define se second
#define pb push_back
#define umax( x , y ) x = max( x , (y) )
#define umin( x , y ) x = min( x , (y) )
#define For( i , a ) for(int i=1;i<=a;i++)
#define ort (b+s)/2
#define y2 asrwjaelkf
#define y1 asseopirwjaelkf

using namespace std;

const int maxn = 150020;
const int kokn = 390;
const int MOd = 1e9+7;

typedef long long Lint;
typedef long double db;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;

int a, b;
vector<ii> w[maxn];
vector<int> v[maxn];
int used[maxn];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    a = N;
    b = M;

    for(int i=0;i<b;i++) {
        int j = R[i][0];
        int k = R[i][1];
        w[j].pb( ii( k, L[i] ) );
        w[k].pb( ii( j, L[i] ) );
    }
    priority_queue<ii> q;
    for(int i=0;i<K;i++) {
        q.push( ii( 0, P[i] ) );
        used[P[i]] = 1;
    }

    while( !q.empty() ) {
        int t = q.top().se;
        int mal = -q.top().fi;
        q.pop();
        used[t]++;
        if( used[t] == 1 || used[t] > 2 ) continue;
        if( t == 0 ) {
            return mal;
        }
        for(int i=0;i<w[t].size();i++)
            q.push( ii( -(mal+w[t][i].se), w[t][i].fi ) );
    }
    assert(0);
    return -1;
}

Compilation message

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

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 127020 KB Output is correct
2 Correct 0 ms 127020 KB Output is correct
3 Correct 0 ms 127020 KB Output is correct
4 Correct 6 ms 127152 KB Output is correct
5 Correct 0 ms 127156 KB Output is correct
6 Correct 3 ms 127020 KB Output is correct
7 Correct 3 ms 127152 KB Output is correct
8 Correct 3 ms 127020 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 127296 KB Output is correct
2 Correct 0 ms 127020 KB Output is correct
3 Correct 6 ms 127152 KB Output is correct
4 Correct 9 ms 127708 KB Output is correct
5 Correct 3 ms 127788 KB Output is correct
6 Correct 0 ms 127020 KB Output is correct
7 Correct 6 ms 127152 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 719 ms 176712 KB Output is correct
2 Correct 116 ms 131772 KB Output is correct
3 Correct 116 ms 132960 KB Output is correct
4 Correct 793 ms 166784 KB Output is correct
5 Correct 433 ms 174572 KB Output is correct
6 Correct 46 ms 129396 KB Output is correct
7 Correct 636 ms 146156 KB Output is correct