Submission #649388

#	Time	Username	Problem	Language	Result	Execution time	Memory
649388		mychecksedad	Crocodile's Underground City (IOI11_crocodile)	C++17	46 / 100	16 ms	24156 KiB

crocodile

#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 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11