oj.uz

Submission #52112

# Submission time Handle Problem Language Result Execution time Memory
52112 2018-06-24T02:04:15 Z 노영훈(#1330, Diuven) Crocodile's Underground City (IOI11_crocodile) C++11
0 / 100
 5 ms 2868 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 cnt[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(cnt[i]>=2) Q.push({i,0});

    while(!Q.empty()){
        ele q=Q.top(); Q.pop();
        int v=q.to; ll d1=q.c1, d2=q.c2;
        if(D1[v]!=d1 || D2[v]!=d2) continue;
        for(edge &e:G[v]){
            int x=e.to; ll c=e.co, now=D2[v]+c;
            cnt[x]++;
            pll old=pll(D1[x], D2[x]);
            if(D2[x]>now) D2[x]=now;
            if(D1[x]>D2[x]) swap(D1[x], D2[x]);
            if(cnt[x]==2 || (cnt[x]>=2 && old!=pll(D1[x],D2[x]))){
                Q.push({x,D1[x],D2[x]});
            }
        }
    }
    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);
    for(int i=0; i<K; i++)
        cnt[P[i]]=10, D1[P[i]]=D2[P[i]]=0;
    return solve();
}

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2800 KB Output is correct
3 Incorrect 5 ms 2868 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2800 KB Output is correct
3 Incorrect 5 ms 2868 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2800 KB Output is correct
3 Incorrect 5 ms 2868 KB Output isn't correct
4 Halted 0 ms 0 KB -