oj.uz

Submission #649388

# Submission time Handle Problem Language Result Execution time Memory
649388 2022-10-10T07:10:06 Z mychecksedad Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 16 ms 24156 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long int ll;
const int X = 1e6, MOD = 1e9+7;



int n, m;
vector<ll> dp[2];
vector<pair<int, ll>> g[X];
bitset<X> is, vis;

void dfs(int v, int p){
    if(is[v]){
        return;
    }
    vector<ll> dist;
    vis[v] = 1;
    dp[0][v] = dp[1][v] = MOD;
    for(auto k: g[v]){
        int u = k.first, e = k.second;
        if(u == p) continue;
        if(!vis[u])
            dfs(u, v);
        dist.pb(dp[1][u] + e);
    }
    sort(dist.begin(), dist.end());
    // cout << '\n';
    // cout << v << ' ';
    // for(int x: dist) cout << x << ' ';
    dp[0][v] = dist[0];
    if(dist.size() == 1) dp[1][v] = MOD;
    else dp[1][v] = dist[1];
    // cout << dp[0][v] << ' ' << dp[1][v] << ' ' << v << '\n';
}

int travel_plan(int F, int M, int R[][2], int L[], int K, int P[]){ 
    n = F;
    m = M;
    dp[0].resize(n);
    dp[1].resize(n);
    for(int i = 0; i < K; ++i) is[P[i]] = 1;
    for(int i = 0; i < m; ++i){
        g[R[i][0]].pb({R[i][1], L[i]});
        g[R[i][1]].pb({R[i][0], L[i]});
    }
    dfs(0, 0);

    return dp[1][0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 16 ms 23764 KB Output is correct
4 Correct 12 ms 24020 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 12 ms 23872 KB Output is correct
7 Correct 12 ms 23912 KB Output is correct
8 Correct 13 ms 23892 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 16 ms 23764 KB Output is correct
4 Correct 12 ms 24020 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 12 ms 23872 KB Output is correct
7 Correct 12 ms 23912 KB Output is correct
8 Correct 13 ms 23892 KB Output is correct
9 Correct 16 ms 24156 KB Output is correct
10 Incorrect 12 ms 23764 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 16 ms 23764 KB Output is correct
4 Correct 12 ms 24020 KB Output is correct
5 Correct 12 ms 23892 KB Output is correct
6 Correct 12 ms 23872 KB Output is correct
7 Correct 12 ms 23912 KB Output is correct
8 Correct 13 ms 23892 KB Output is correct
9 Correct 16 ms 24156 KB Output is correct
10 Incorrect 12 ms 23764 KB Output isn't correct
11 Halted 0 ms 0 KB -