oj.uz

답안 #846326

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
846326 2023-09-07T13:32:39 Z 12345678 악어의 지하 도시 (IOI11_crocodile) C++17
46 / 100
 159 ms 262144 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5;
ll dp[nx];
bool ed[nx];
vector<vector<pair<ll, ll>>> d(nx);

void dfs(int u, int p)
{
    ll mn1(LLONG_MAX), mn2(LLONG_MAX);
    for (auto [v, w]:d[u]) 
    {
        if (v==p) continue;
        dfs(v, u);
        if (dp[v]+w<mn1) swap(mn1, mn2), mn1=dp[v]+w;
        else if (dp[v]+w<mn2) mn2=dp[v]+w;
    }
    dp[u]=(ed[u]==1)?0:mn2;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    for (int i=0; i<M; i++) d[R[i][0]].push_back({R[i][1], L[i]}), d[R[i][1]].push_back({R[i][0], L[i]});
    for (int i=0; i<K; i++) ed[P[i]]=1;
    dfs(0, 0);
    return dp[0];
}

Subtask #1
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 2 ms 6744 KB Output is correct
3 Correct 2 ms 6744 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Correct 2 ms 6744 KB Output is correct
6 Correct 3 ms 6744 KB Output is correct
7 Correct 2 ms 7004 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct

Subtask #2
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 2 ms 6744 KB Output is correct
3 Correct 2 ms 6744 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Correct 2 ms 6744 KB Output is correct
6 Correct 3 ms 6744 KB Output is correct
7 Correct 2 ms 7004 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct
9 Runtime error 159 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 2 ms 6744 KB Output is correct
3 Correct 2 ms 6744 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Correct 2 ms 6744 KB Output is correct
6 Correct 3 ms 6744 KB Output is correct
7 Correct 2 ms 7004 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct
9 Runtime error 159 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -