Submission #1124593

#TimeUsernameProblemLanguageResultExecution timeMemory
1124593knot222Crocodile's Underground City (IOI11_crocodile)C++20
0 / 100
1 ms576 KiB
#include "crocodile.h" #include <bits/stdc++.h> #define ll long long int using namespace std; int ex[10005]; ll dp[10005][2]; int par[10005]; int visited[10005]; vector<pair<int,ll>> adj[10005]; void dfs(int n) { visited[n] = 1; for (auto u : adj[n]) { if (!visited[u.first]) { dfs(u.first); } else { par[n] = u.first; } } dp[n][0] = LLONG_MAX/2; dp[n][1] = LLONG_MAX/2; if (ex[n]) { dp[n][0] = 0; dp[n][1] = 0; } else { for (auto u : adj[n]) { int X = u.first; if (X!=par[n]) { if (dp[n][1]>dp[X][1]+u.second) { dp[n][1] = dp[X][1]+u.second; if (dp[n][0]>dp[n][1]) { swap(dp[n][0], dp[n][1]); } } } } } } int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) { for (int i=0;i<N;i++) { par[i] = -1; } for (int i=0;i<K;i++) { ex[P[i]] = 1; } for (int i=0;i<M;i++) { adj[R[i][0]].push_back(make_pair(R[i][1], L[i])); adj[R[i][1]].push_back(make_pair(R[i][0], L[i])); } dfs(0); for (int i=0;i<N;i++) { cout << dp[i][0] << ' '<< dp[i][1] << endl; } for (int i=0;i<5;i++) { cout << par[i] << ' '; } return dp[0][1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...