Submission #893112

#TimeUsernameProblemLanguageResultExecution timeMemory
893112raul2008487Dreaming (IOI13_dreaming)C++17
18 / 100
51 ms15884 KiB
#include<bits/stdc++.h> #include "dreaming.h" #define ll long long #define pll pair<ll,ll> #define vl vector<ll> #define fi first #define se second #define in insert #define all(v) v.begin(),v.end() const int sz = 100005; const ll inf = 1000000000000000; using namespace std; vector<pair<ll,ll>> adj[sz]; ll dis[sz][2], center, v1, v2, mx, cnt = -1; bool used[sz]; vector<vector<ll>> path; void trav(ll node){ used[node] = 1; path[cnt].push_back(node); for(pll edge: adj[node]){ if(!used[edge.fi]){ trav(edge.fi); } } } void dfs(ll node, ll we, ll p){ if(we > mx){ v2 = node; mx = we; } for(pll edge: adj[node]){ if(edge.fi != p){ dfs(edge.fi, we + edge.se, node); } } } void caldis(ll node, ll we, ll p, ll type){ dis[node][type] = we; for(pll edge: adj[node]){ if(edge.fi != p){ caldis(edge.fi, we + edge.se, node, type); } } } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { ll n = N, m = M, i, j; for(i=1;i<=m;i++){ adj[A[i]].push_back({B[i], T[i]}); adj[B[i]].push_back({A[i], T[i]}); } for(i=0;i<n;i++){ if(!used[i]){ cnt++; path.push_back(vl(0)); trav(i); } } multiset<ll> ms; ll res = -inf; for(i=0;i<=cnt;i++){ mx = -inf, v1 = -1, v2 = -1; dfs(path[i][0], 0, -1); v1 = v2; mx = -inf; dfs(v1, 0, -1); caldis(v1, 0, -1, 0);caldis(v2, 0, -1, 1); ll pc = path[i][0], pb = max(dis[pc][0], dis[pc][1]); for(ll x: path[i]){ if (max(dis[x][0], dis[x][1]) < max(dis[pc][0], dis[pc][1])) pc = x; } ms.in( max(dis[pc][0], dis[pc][1]) ); res = max(res, mx); //ans = max(ans, pb); } if (cnt == 0) return max(res, *ms.begin()); auto it = ms.end(); it--; it--; auto it1 = it; it1--; if (cnt == 1){ return max(res, *ms.rbegin() + *it + L); assert(0);} return max({res, *ms.rbegin() + *it + L, *it + *it1 + 2*L}); }

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:67:29: warning: unused variable 'pb' [-Wunused-variable]
   67 |         ll pc = path[i][0], pb = max(dis[pc][0], dis[pc][1]);
      |                             ^~
dreaming.cpp:46:25: warning: unused variable 'j' [-Wunused-variable]
   46 |     ll n = N, m = M, i, 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...