Submission #846128

#TimeUsernameProblemLanguageResultExecution timeMemory
846128detaomegaDreaming (IOI13_dreaming)C++14
0 / 100
17 ms4440 KiB
#include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std; #include "dreaming.h" const int maxn = 1e4 + 5; vector<pair<int,int>> G[maxn]; vector<int> vis(maxn, 0); vector<int> dp(maxn, 0); int getDiameter(int n) { queue<int> q; vector<int> dis(maxn, -1); q.push(1); dis[1] = 0; while (q.size()) { int u = q.front(); q.pop(); for (auto e : G[u]) { int v = e.first; if (dis[v] == -1) { dis[v] = dis[u] + e.second; q.push(v); } } } int now = 0, mx = 0; for (int i = 1; i <= n; i++) { if (mx < dis[i]) { mx = dis[i]; now = i; } dis[i] = -1; } q.push(now); dis[now] = 0; while (q.size()) { int u = q.front(); q.pop(); for (auto e : G[u]) { int v = e.first; if (dis[v] == -1) { dis[v] = dis[u] + e.second; q.push(v); } } } return *max_element(dis.begin(), dis.end()); } int dfs(int now, int fa) { int mx = 0; for (auto e : G[now]) { if (e.first != fa) { mx = max(mx, dfs(e.first, now) + e.second); } } return mx; } int dfs1(int now, int fa) { int mx = dp[now]; vis[now] = true; for (auto e : G[now]) { if (e.first != fa) { mx = min(dfs1(e.first, now), mx); } } return mx; } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { for (int i = 0; i < M; i++) { // cout << A[i] << " " << B[i]; A[i]++; B[i]++; G[A[i]].emplace_back(B[i], T[i]); G[B[i]].emplace_back(A[i], T[i]); } if (N == 1) { return 0; } if (N == M + 1) { return getDiameter(N); } if (N == 2) { return L; } if (M == 0) { return L * 2; } for (int i = 1; i <= N; i++) { dp[i] = dfs(i, 0); } int ans = 0; for (int i = 1; i <= N; i++) { if (!vis[i]) { cout << i - 1 << " " << dfs1(i, 0) << "\n"; ans = ans + dfs1(i, 0); } } return ans + L; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...