oj.uz

Submission #289707

# Submission time Handle Problem Language Result Execution time Memory
289707 2020-09-02T23:05:42 Z b00n0rp Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 1145 ms 71032 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
typedef vector <int> vi;
typedef vector<vi> vvi;
typedef map<int,int> mii;
typedef pair<int,int> pii;
#define pb push_back
#define INF 1000000000000000
#define mp make_pair
#define MOD 1000000007
#define F first
#define S second
const double PI=3.141592653589793238462643383279502884197169399375105820974944;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REPD(i,n) for(int i=(n);i>=0;i--)
#define FORD(i,a,b) for(int i=(a);i>=b;i--)
#define all(v) v.begin(),v.end()
#define itr ::iterator it
#define WL(t) while(t --)
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define remin(a,b) (a) = min((a),(b))
#define remax(a,b) (a) = max((a),(b))

int n,m,k;
vector<pii> adj[100005];
bool exi[100005];
int dist[100005],dist2[100005];

int dijkstra(){
    set<pii>pq;
    REP(i,n){
        if(exi[i]){
            pq.insert({0,i});
            dist[i]=dist2[i]=0;
        }
        else{
            dist[i]=dist2[i]=INF;
            pq.insert({INF,i});
        }
    }
    while(!pq.empty()){
        int u = pq.begin()->S;
        pq.erase(pq.begin());
        if(!u) return dist2[u];
        for(auto x:adj[u]){
            int v = x.F;
            int tot = dist2[u]+x.S;
            if(tot < dist[v]){
                pq.erase({dist2[v],v});
                dist2[v] = dist[v];
                dist[v] = tot;
                pq.insert({dist2[v],v});
            }
            else if(tot < dist2[v]){
                pq.erase({dist2[v],v});             
                dist2[v] = tot;
                pq.insert({dist2[v],v});
            }
        }
    }
}

signed travel_plan(signed N, signed M, signed R[][2], signed L[], signed K, signed P[]){
    n = N;
    m = M;
    k = K;
    REP(i,m){
        int u,v,w;
        u = R[i][0];
        v = R[i][1];
        w = L[i];
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    REP(i,n) exi[i] = 0;
    REP(i,k){
        int x; x = P[i];
        exi[x] = 1;
    }
    return (signed)dijkstra();
}

Compilation message

crocodile.cpp: In function 'll dijkstra()':
crocodile.cpp:35:13: warning: control reaches end of non-void function [-Wreturn-type]
   35 |     set<pii>pq;
      |             ^~

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2816 KB Output is correct
4 Correct 3 ms 2816 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct
9 Correct 4 ms 3072 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 3 ms 2816 KB Output is correct
12 Correct 6 ms 3328 KB Output is correct
13 Correct 7 ms 3456 KB Output is correct
14 Correct 2 ms 2688 KB Output is correct
15 Correct 3 ms 2816 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2816 KB Output is correct
4 Correct 3 ms 2816 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct
9 Correct 4 ms 3072 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 3 ms 2816 KB Output is correct
12 Correct 6 ms 3328 KB Output is correct
13 Correct 7 ms 3456 KB Output is correct
14 Correct 2 ms 2688 KB Output is correct
15 Correct 3 ms 2816 KB Output is correct
16 Correct 759 ms 65264 KB Output is correct
17 Correct 163 ms 21624 KB Output is correct
18 Correct 180 ms 23160 KB Output is correct
19 Correct 1145 ms 71032 KB Output is correct
20 Correct 338 ms 55288 KB Output is correct
21 Correct 71 ms 11128 KB Output is correct
22 Correct 411 ms 52600 KB Output is correct