Submission #1073695

#TimeUsernameProblemLanguageResultExecution timeMemory
1073695andrewpDreaming (IOI13_dreaming)C++14
14 / 100
34 ms12840 KiB
//Dedicated to my love, ivaziva #include <bits/stdc++.h> #include "dreaming.h" using namespace std; using pii = pair<int, int>; using ll = int64_t; #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define dbg(x) cerr << #x << ": " << x << '\n'; constexpr int mxN = 1e5 + 20; vector<pii> g[mxN]; int dp[mxN], dpp[mxN], ps[mxN], ss[mxN]; int current_root = 0, sz = 0; bool vis[mxN]; vector<int> vec; void dfs1(int x, int p) { sz++; vis[x] = true; vec.push_back(x); for (auto ptr: g[x]) { if (ptr.first != p) { dfs1(ptr.first, x); dp[x] = max(dp[x], dp[ptr.first] + ptr.second); } } } void dfs2(int x, int p) { for (auto ptr: g[x]) { if (ptr.first != p) { if (x == current_root) { dpp[ptr.first] += ptr.second; } else { dpp[ptr.first] = dpp[x] + ptr.second; } dfs2(ptr.first, x); } } } int travelTime(int N, int M, int L, int* A, int* B, int* T) { for (int i = 0; i < M; i++) { g[A[i]].push_back({B[i], T[i]}); g[B[i]].push_back({A[i], T[i]}); } for (int i = 0; i < N; i++) { dp[i] = 0, dpp[i] = 0; } vector<int> diams, anss; for (int i = 0; i < N; i++) { if (!vis[i]) { vec.clear(); sz = 0; dfs1(i, -1); if (sz == 1) { continue; } ps[0] = dp[g[i][0].first] + g[i][0].second; // if (i == 1) dbg(ps[0]); for (int j = 1; j < g[i].size(); j++) { ps[j] = max(ps[j - 1], dp[g[i][j].first] + g[i][j].second); // if (i == 1) dbg(ps[j]); } ss[g[i].size() - 1] = dp[g[i].back().first] + g[i].back().second; for (int j = g[i].size() - 2; j >= 0; j--) { ss[j] = max(ss[j + 1], dp[g[i][j].first] + g[i][j].second); } for (int j = 0; j < g[i].size(); j++) { dpp[g[i][j].first] = max((j >= 1 ? ps[j - 1] : 0), ss[j + 1]); } for (int j = 0; j <= g[i].size() + 5; j++) { ps[j] = 0, ss[j] = 0; } current_root = i; dfs2(i, -1); int mn = (int)(2e9), di = 0; for (int x: vec) { // cerr << i << ' ' << x << ' ' << dp[x] << ' ' << dpp[x] << '\n'; int curr = max(dpp[x], dp[x]); di = max(di, dpp[x] + dp[x]); if (mn > curr) { mn = curr; } } diams.push_back(di); anss.push_back(mn); } } int ans = max(diams[0], diams[1]); ans = max(ans, anss[0] + anss[1] + L); return ans; } /*int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cerr.tie(nullptr); int n, m, l; cin >> n >> m >> l; int a[m], b[m], t[m]; for (int i = 0; i < m; i++) { cin >> a[i] >> b[i] >> t[i]; } int ans = travelTime(n, m, l, a, b, t); cout << ans << '\n'; return 0; }*/ /* 12 8 2 0 8 4 8 2 2 2 7 4 5 11 3 5 1 7 1 3 1 1 9 5 10 6 3 12 7 2 0 8 4 8 2 2 2 7 4 5 11 3 5 1 7 1 3 1 1 9 5 */

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:64:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             for (int j = 1; j < g[i].size(); j++) {
      |                             ~~^~~~~~~~~~~~~
dreaming.cpp:72:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             for (int j = 0; j < g[i].size(); j++) {
      |                             ~~^~~~~~~~~~~~~
dreaming.cpp:75:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |             for (int j = 0; j <= g[i].size() + 5; j++) {
      |                             ~~^~~~~~~~~~~~~~~~~~
#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...