| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 402706 | 2021-05-12T09:20:44 Z | Antekb | 악어의 지하 도시 (IOI11_crocodile) | C++14 | 817 ms | 61560 KB |
#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define mp(x, y) make_pair(x ,y)
typedef long long ll;
const ll INF=1e18;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
ll dist[N], dist2[N];
vector<pair<int, int> > E[N];
for(int i=0; i<M; i++){
E[R[i][0]].push_back(mp(R[i][1], L[i]));
E[R[i][1]].push_back(mp(R[i][0], L[i]));
}
for(int i=0; i<N;i++)dist[i]=dist2[i]=INF;
for(int i=0; i<K; i++)dist[P[i]]=dist2[P[i]]=0;
set<pair<ll, int> > S;
for(int i=0;i<N; i++){
S.insert(mp(dist[i], i));
}
while(S.size()){
int v=(*S.begin()).nd;
S.erase(S.begin());
if(v==0){
return dist[v];
}
for(auto i:E[v]){
if(dist[v]+i.nd<dist[i.st]){
S.erase(S.find(mp(dist[i.st], i.st)));
if(dist[v]+i.nd>dist2[i.st])dist[i.st]=dist[v]+i.nd;
else{
dist[i.st]=dist2[i.st];
dist2[i.st]=dist[v]+i.nd;
}
S.insert(mp(dist[i.st], i.st));
}
}
}
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 204 KB | Output is correct |
| 2 | Correct | 1 ms | 204 KB | Output is correct |
| 3 | Correct | 1 ms | 332 KB | Output is correct |
| 4 | Correct | 2 ms | 460 KB | Output is correct |
| 5 | Correct | 2 ms | 460 KB | Output is correct |
| 6 | Correct | 2 ms | 428 KB | Output is correct |
| 7 | Correct | 2 ms | 460 KB | Output is correct |
| 8 | Correct | 2 ms | 460 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 204 KB | Output is correct |
| 2 | Correct | 1 ms | 204 KB | Output is correct |
| 3 | Correct | 1 ms | 332 KB | Output is correct |
| 4 | Correct | 2 ms | 460 KB | Output is correct |
| 5 | Correct | 2 ms | 460 KB | Output is correct |
| 6 | Correct | 2 ms | 428 KB | Output is correct |
| 7 | Correct | 2 ms | 460 KB | Output is correct |
| 8 | Correct | 2 ms | 460 KB | Output is correct |
| 9 | Correct | 3 ms | 588 KB | Output is correct |
| 10 | Correct | 1 ms | 332 KB | Output is correct |
| 11 | Correct | 2 ms | 444 KB | Output is correct |
| 12 | Correct | 4 ms | 696 KB | Output is correct |
| 13 | Correct | 4 ms | 716 KB | Output is correct |
| 14 | Correct | 1 ms | 332 KB | Output is correct |
| 15 | Correct | 2 ms | 332 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 204 KB | Output is correct |
| 2 | Correct | 1 ms | 204 KB | Output is correct |
| 3 | Correct | 1 ms | 332 KB | Output is correct |
| 4 | Correct | 2 ms | 460 KB | Output is correct |
| 5 | Correct | 2 ms | 460 KB | Output is correct |
| 6 | Correct | 2 ms | 428 KB | Output is correct |
| 7 | Correct | 2 ms | 460 KB | Output is correct |
| 8 | Correct | 2 ms | 460 KB | Output is correct |
| 9 | Correct | 3 ms | 588 KB | Output is correct |
| 10 | Correct | 1 ms | 332 KB | Output is correct |
| 11 | Correct | 2 ms | 444 KB | Output is correct |
| 12 | Correct | 4 ms | 696 KB | Output is correct |
| 13 | Correct | 4 ms | 716 KB | Output is correct |
| 14 | Correct | 1 ms | 332 KB | Output is correct |
| 15 | Correct | 2 ms | 332 KB | Output is correct |
| 16 | Correct | 582 ms | 52816 KB | Output is correct |
| 17 | Correct | 146 ms | 20756 KB | Output is correct |
| 18 | Correct | 157 ms | 22292 KB | Output is correct |
| 19 | Correct | 817 ms | 61560 KB | Output is correct |
| 20 | Correct | 315 ms | 47192 KB | Output is correct |
| 21 | Correct | 63 ms | 8096 KB | Output is correct |
| 22 | Correct | 369 ms | 46348 KB | Output is correct |