oj.uz

Submission #334655

# Submission time Handle Problem Language Result Execution time Memory
334655 2020-12-09T16:28:35 Z ijxjdjd Crocodile's Underground City (IOI11_crocodile) C++11
100 / 100
 635 ms 61668 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;

typedef long long ll;
typedef string str;
typedef double db;
typedef long double ld;

typedef pair<int, int> pi;
typedef  pair<long, long> pl;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;


#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define FR(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define RF(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MAXN = (int)(1e5)+5;
const int INF = (int)(1e9) + 5;
int from[MAXN];
int dist[MAXN];
int dist2[MAXN];
vector<pair<int, int>> adj[MAXN];
void dijkstra(int K, int P[]) {
    FR(i, MAXN) {
        dist[i] = INF;
        from[i] = 0;
        dist2[i] = INF;
    }
    priority_queue<pi,vector<pair<int,int>>,greater<pair<int,int>>> q;
    FR(i, K) {
        from[P[i]] = 1;
        dist[P[i]] = 0;
        dist2[P[i]] = 0;
        q.push({0,P[i]});
    }
    while(!q.empty())
    {
        pair<int,int> p = q.top();
        q.pop();
        int u = p.second, d = p.first;
        if (from[u] == 0) {
            from[u]++;
            continue;
        }
        else if (from[u] == 1) {
            from[u]++;
            for(pi pr : adj[u]) {
                int v = pr.second;
                int next_dist = d + pr.first;
                if(next_dist < dist[v])
                {
                    dist2[v] = dist[v];
                    dist[v] = next_dist;
                    q.push({next_dist,v});
                }
                else if (next_dist < dist2[v]) {
                    dist2[v] = next_dist;
                    q.push({next_dist,v});
                }
            }

        }
    }
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    for (int i = 0; i < M; i++) {
        adj[R[i][1]].push_back({L[i], R[i][0]});
        adj[R[i][0]].push_back({L[i], R[i][1]});
    }
    dijkstra(K, P);
    return dist2[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3820 KB Output is correct
2 Correct 4 ms 3820 KB Output is correct
3 Correct 3 ms 3820 KB Output is correct
4 Correct 4 ms 3968 KB Output is correct
5 Correct 4 ms 3948 KB Output is correct
6 Correct 3 ms 3948 KB Output is correct
7 Correct 4 ms 3948 KB Output is correct
8 Correct 4 ms 3948 KB Output is correct
9 Correct 5 ms 4204 KB Output is correct
10 Correct 3 ms 3820 KB Output is correct
11 Correct 4 ms 3948 KB Output is correct
12 Correct 6 ms 4332 KB Output is correct
13 Correct 6 ms 4332 KB Output is correct
14 Correct 3 ms 3948 KB Output is correct
15 Correct 4 ms 3948 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3820 KB Output is correct
2 Correct 4 ms 3820 KB Output is correct
3 Correct 3 ms 3820 KB Output is correct
4 Correct 4 ms 3968 KB Output is correct
5 Correct 4 ms 3948 KB Output is correct
6 Correct 3 ms 3948 KB Output is correct
7 Correct 4 ms 3948 KB Output is correct
8 Correct 4 ms 3948 KB Output is correct
9 Correct 5 ms 4204 KB Output is correct
10 Correct 3 ms 3820 KB Output is correct
11 Correct 4 ms 3948 KB Output is correct
12 Correct 6 ms 4332 KB Output is correct
13 Correct 6 ms 4332 KB Output is correct
14 Correct 3 ms 3948 KB Output is correct
15 Correct 4 ms 3948 KB Output is correct
16 Correct 520 ms 59104 KB Output is correct
17 Correct 80 ms 14188 KB Output is correct
18 Correct 110 ms 15724 KB Output is correct
19 Correct 635 ms 61668 KB Output is correct
20 Correct 308 ms 50796 KB Output is correct
21 Correct 41 ms 8684 KB Output is correct
22 Correct 348 ms 47084 KB Output is correct