Submission #893094

#TimeUsernameProblemLanguageResultExecution timeMemory
893094raul2008487Dreaming (IOI13_dreaming)C++17
18 / 100
54 ms15312 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, ans = 0; 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); } } array<ll, 3> bp = {-1, -1, -1}; ll worst = inf; for(i=0;i<=cnt;i++){ mx = -1, v1 = -1, v2 = -1; dfs(path[i][0], 0, -1); v1 = v2; mx = -1; dfs(v1, 0, -1); caldis(v1, 0, -1, 0);caldis(v2, 0, -1, 1); ans = max(ans, mx); ll pc = path[i][0], pb = max(dis[pc][0], dis[pc][1]); for(auto x: path[i]){ if(max(dis[x][0], dis[x][1]) < pb){ pb = max(dis[x][0], dis[x][1]); } } worst = min(worst, pb); //ans = max(ans, pb); if(pb > bp[0]){ bp[2] = bp[1]; bp[1] = bp[0]; bp[0] = pb; } else if(pb > bp[1]){ bp[2] = bp[1]; bp[1] = pb; } else if(pb > bp[2]){ bp[2] = pb; } } if(cnt == 0){ return ans; } ans = max(ans, bp[0] + bp[1] + L); if(bp[2] != -1){ ans = max(ans, bp[1] + bp[2] + 2*L); } return ans; }

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:46:25: warning: unused variable 'j' [-Wunused-variable]
   46 |     ll n = N, m = M, i, j, ans = 0;
      |                         ^
#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...