oj.uz

Submission #93950

# Submission time Handle Problem Language Result Execution time Memory
93950 2019-01-13T16:50:17 Z someone_aa Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 323 ms 263168 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
int dpf[maxn], dps[maxn];
vector<pair<int,int> > g[maxn];

void dfs(int node, int p) {
    if(g[node].size() == 1) {
        dps[node] = dpf[node] = 0LL;
        return;
    }

    vector<ll>dp;
    for(auto i:g[node]) {
        if(i.first != p) {
            dfs(i.first, node);
            dp.pb(dps[i.first] + i.second);
        }
    }

    sort(dp.begin(), dp.end());
    if(g[node].size() == 1) return;
    dpf[node] = dp[0];
    dps[node] = dp[1];
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    for(int i=0;i<M;i++) {
        g[R[i][0]].pb(mp(R[i][1], L[i]));
        g[R[i][1]].pb(mp(R[i][0], L[i]));
    }
    dfs(0, -1);
    return int(dps[0]);
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2684 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2756 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 4 ms 2808 KB Output is correct
7 Correct 4 ms 3064 KB Output is correct
8 Correct 4 ms 2808 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2684 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2756 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 4 ms 2808 KB Output is correct
7 Correct 4 ms 3064 KB Output is correct
8 Correct 4 ms 2808 KB Output is correct
9 Runtime error 323 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2684 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2756 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 4 ms 2808 KB Output is correct
7 Correct 4 ms 3064 KB Output is correct
8 Correct 4 ms 2808 KB Output is correct
9 Runtime error 323 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -