oj.uz

Submission #52130

# Submission time Handle Problem Language Result Execution time Memory
52130 2018-06-24T06:03:09 Z 노영훈(#1330, Diuven) Crocodile's Underground City (IOI11_crocodile) C++11
100 / 100
 1545 ms 134216 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const int MX=100010;
const ll inf=2e16;

struct edge {
    int to;
    ll co;
};

vector<edge> G[MX];

int n;
ll D1[MX], D2[MX];
int T1[MX], T2[MX];

struct ele {
    int to; ll c1, c2;
    bool operator < (const ele &e) const {
        return pll(c1,c2) > pll(e.c1, e.c2);
    }
};

ll solve(){
    priority_queue<ele> Q;
    for(int i=0; i<n; i++){
        if(D2[i]==0) Q.push({i,0,0});
    }

    while(!Q.empty()){
        ele e=Q.top(); Q.pop();
        int v=e.to; ll d1=e.c1, d2=e.c2;
        if(D1[v]!=d1 || D2[v]!=d2) continue;

        for(edge &e:G[v]){
            int x=e.to; ll c=e.co, now=d2+c;
            pll old=pll(D1[x], D2[x]);
            if(T1[x]==v || T2[x]==v){
                if(T1[x]==v){
                    D1[x]=min(D1[x], now);
                }
                if(T2[x]==v){
                    D2[x]=min(D2[x], now);
                }
                if(D1[x]>D2[x]) swap(D1[x], D2[x]), swap(T1[x], T2[x]);
            }
            else{
                if(D2[x]>now) D2[x]=now, T2[x]=v;
                if(D1[x]>D2[x]) swap(D1[x], D2[x]), swap(T1[x], T2[x]);
            }
            if(old!=pll(D1[x], D2[x])) Q.push({x,D1[x],D2[x]});
        }
    }
    // for(int i=0; i<n; i++)
    //     cout<<D1[i]<<' ';
    // cout<<'\n';
    // for(int i=0; i<n; i++)
    //     cout<<D2[i]<<' ';
    // cout<<'\n';

    return D2[0];
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    n=N;
    for(int i=0; i<M; i++){
        int x=R[i][0], y=R[i][1];
        G[x].push_back({y,L[i]});
        G[y].push_back({x,L[i]});
    }
    fill(D1, D1+n, inf);
    fill(D2, D2+n, inf);
    fill(T1, T1+n, -1);
    fill(T2, T2+n, -1);
    for(int i=0; i<K; i++){
        int v=P[i];
        D1[v]=D2[v]=0;
        T1[v]=T2[v]=v;
    }
    return solve();
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 5 ms 2788 KB Output is correct
3 Correct 5 ms 2868 KB Output is correct
4 Correct 6 ms 3048 KB Output is correct
5 Correct 5 ms 3048 KB Output is correct
6 Correct 4 ms 3048 KB Output is correct
7 Correct 5 ms 3068 KB Output is correct
8 Correct 5 ms 3212 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 5 ms 2788 KB Output is correct
3 Correct 5 ms 2868 KB Output is correct
4 Correct 6 ms 3048 KB Output is correct
5 Correct 5 ms 3048 KB Output is correct
6 Correct 4 ms 3048 KB Output is correct
7 Correct 5 ms 3068 KB Output is correct
8 Correct 5 ms 3212 KB Output is correct
9 Correct 7 ms 3432 KB Output is correct
10 Correct 6 ms 3432 KB Output is correct
11 Correct 5 ms 3432 KB Output is correct
12 Correct 10 ms 3960 KB Output is correct
13 Correct 7 ms 4204 KB Output is correct
14 Correct 5 ms 4204 KB Output is correct
15 Correct 5 ms 4204 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 5 ms 2788 KB Output is correct
3 Correct 5 ms 2868 KB Output is correct
4 Correct 6 ms 3048 KB Output is correct
5 Correct 5 ms 3048 KB Output is correct
6 Correct 4 ms 3048 KB Output is correct
7 Correct 5 ms 3068 KB Output is correct
8 Correct 5 ms 3212 KB Output is correct
9 Correct 7 ms 3432 KB Output is correct
10 Correct 6 ms 3432 KB Output is correct
11 Correct 5 ms 3432 KB Output is correct
12 Correct 10 ms 3960 KB Output is correct
13 Correct 7 ms 4204 KB Output is correct
14 Correct 5 ms 4204 KB Output is correct
15 Correct 5 ms 4204 KB Output is correct
16 Correct 805 ms 87780 KB Output is correct
17 Correct 173 ms 87780 KB Output is correct
18 Correct 158 ms 87780 KB Output is correct
19 Correct 1545 ms 134216 KB Output is correct
20 Correct 384 ms 134216 KB Output is correct
21 Correct 57 ms 134216 KB Output is correct
22 Correct 484 ms 134216 KB Output is correct