Submission #900544

#TimeUsernameProblemLanguageResultExecution timeMemory
900544gun_ganDreaming (IOI13_dreaming)C++17
18 / 100
36 ms15056 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MX = 1e5 + 5; int N, M, L; vector<pair<int,int>> g[MX]; bool vis[MX]; int cur = 0, mx = 0, z = 0, len = 0; vector<int> vec; int p = 0, q = 0; pair<int,int> par[MX]; void dfs(int v) { vis[v] = 1; vec.push_back(v); if(cur > mx) { mx = cur; z = v; } for(auto [u, w] : g[v]) { if(!vis[u]) { if(cur + w > len / 2 && !p && len > 0) { p = cur; q = len - cur; } cur += w; par[u] = {v, w}; dfs(u); cur -= w; } } } vector<pair<int,int>> P; 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 = 1; i <= N; i++) { if(vis[i]) continue; vec.clear(); cur = 0, mx = 0, z = 0, len = 0; dfs(i); for(auto x : vec) { vis[x] = 0; } if(vec.size() == 1) { for(auto x : vec) { vis[x] = 1; } P.push_back({0, 0}); continue; } if(vec.size() == 2) { for(auto x : vec) { vis[x] = 1; } P.push_back({mx, 0}); continue; } vec.clear(); int tz = z; cur = 0, mx = 0, z = 0; dfs(tz); len = mx; int k = z, sum = 0; while(k != tz) { if(sum + par[k].second > len / 2 && sum <= len / 2) { p = sum; q = len - sum; } sum += par[k].second; k = par[k].first; } vec.clear(); P.push_back({max(p, q), min(p, q)}); } sort(P.rbegin(), P.rend()); int ans = 0; for(auto [x, y] : P) { ans = max(ans, x + y); } for(int i = 1; i < P.size(); i++) { auto [x, y] = P[i]; ans = max(ans, P[0].first + L + x); } if(P.size() > 2) { ans = max(ans, P[1].first + 2 * L + P[2].first); } return ans; }

Compilation message (stderr)

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