oj.uz

Submission #17009

# Submission time Handle Problem Language Result Execution time Memory
17009 2015-11-03T18:29:24 Z murat Crocodile's Underground City (IOI11_crocodile) C++
100 / 100
 696 ms 199988 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

#define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
#define dbg(x) cerr << (#x) << " --> " << (x) << endl

#define foreach(i,x) for(type(x)i=x.begin();i!=x.end();i++)
#define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
#define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)

#define type(x) __typeof(x.begin())

#define orta (bas + son >> 1)
#define sag (k + k + 1)
#define sol (k + k)

#define pb push_back
#define mp make_pair

#define nd second
#define st first

#define endl '\n'

typedef pair < int ,int > pii;

typedef long long ll;

const long long linf = 1e18+5;
const int mod = (int) 1e9 + 7;
const int logN = 17;
const int inf = 1e9;
const int N = 1e6 + 5;

int h[N], n, m, x, y, z, ok[N];
vector< pii > v[N];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    n = N;
    m = M;
    FOR(i, 0, m-1) {
        int x = ++R[i][0],
            y = ++R[i][1];
        v[x].pb(mp(y, L[i]));
        v[y].pb(mp(x, L[i]));
    }

    priority_queue< pii , vector< pii >, greater< pii > > q;

    FOR(i, 0, K-1) {
        ok[P[i]+1] = 1;
        q.push(mp(0, ++P[i]));
    }
    while(!q.empty()) {
        int node = q.top().nd,
            cost = q.top().st;
        q.pop();
        if(!ok[node]) { ok[node] = 1; continue; }
        else if(ok[node] > 1) continue;
        ok[node] = 2;
        if(node == 1) return cost;
        foreach(it, v[node])
            q.push(mp(it->nd + cost, it->st));
    }
    return -1;
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 150616 KB Output is correct
2 Correct 4 ms 150356 KB Output is correct
3 Correct 11 ms 150356 KB Output is correct
4 Correct 5 ms 150972 KB Output is correct
5 Correct 14 ms 150620 KB Output is correct
6 Correct 9 ms 150356 KB Output is correct
7 Correct 10 ms 150356 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 582 ms 199988 KB Output is correct
2 Correct 108 ms 154976 KB Output is correct
3 Correct 128 ms 156164 KB Output is correct
4 Correct 633 ms 190020 KB Output is correct
5 Correct 327 ms 173244 KB Output is correct
6 Correct 60 ms 152600 KB Output is correct
7 Correct 696 ms 169412 KB Output is correct