oj.uz

Submission #465271

# Submission time Handle Problem Language Result Execution time Memory
465271 2021-08-15T12:57:28 Z MohamedFaresNebili Crocodile's Underground City (IOI11_crocodile) C++14
46 / 100
 141 ms 262148 KB 
#include <bits/stdc++.h>
#include "crocodile.h"

using namespace std;
int n, m, k; vector<pair<int, long long>>adj[100000];
vector<int>ex; vector<bool>e; long long dp[100000];
long long dfs(int v, int p)
{
    if(e[v]) return 0;
	if(dp[v]!=-1) return dp[v];
    long long best=1e9, ans=1e9; int node=-1;
    for(auto u:adj[v]) {
        int to=u.first; long long w=u.second;
        if(to==p) continue;
		long long cnt=w+dfs(to, v);
        if(cnt<best) node=to, best=cnt;
    }
    for(auto u:adj[v]) {
        int to=u.first; long long w=u.second;
        if(to==p||to==node) continue;
        ans=min(ans, w+dfs(to, v));
    }
    return dp[v]=ans;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    n=N, m=M, k=K; e.assign(n, false);
	memset(dp, -1, sizeof dp);
    for(int l=0;l<m;l++) {
        int a=R[l][0], b=R[l][1]; long long w=L[l];
        adj[a].push_back({b, w}); adj[b].push_back({a, w});
    }
    for(int l=0;l<k;l++) {
        int i=P[l]; e[i]=true; ex.push_back(i);
    }
    N=dfs(0, -1);
    return N;
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct
3 Correct 3 ms 3404 KB Output is correct
4 Correct 2 ms 3404 KB Output is correct
5 Correct 3 ms 3404 KB Output is correct
6 Correct 2 ms 3404 KB Output is correct
7 Correct 3 ms 3532 KB Output is correct
8 Correct 3 ms 3532 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct
3 Correct 3 ms 3404 KB Output is correct
4 Correct 2 ms 3404 KB Output is correct
5 Correct 3 ms 3404 KB Output is correct
6 Correct 2 ms 3404 KB Output is correct
7 Correct 3 ms 3532 KB Output is correct
8 Correct 3 ms 3532 KB Output is correct
9 Runtime error 141 ms 262148 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct
3 Correct 3 ms 3404 KB Output is correct
4 Correct 2 ms 3404 KB Output is correct
5 Correct 3 ms 3404 KB Output is correct
6 Correct 2 ms 3404 KB Output is correct
7 Correct 3 ms 3532 KB Output is correct
8 Correct 3 ms 3532 KB Output is correct
9 Runtime error 141 ms 262148 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -