Submission #1243837

#TimeUsernameProblemLanguageResultExecution timeMemory
1243837rayan_bdDreaming (IOI13_dreaming)C++20
47 / 100
57 ms20036 KiB
#include <bits/stdc++.h> #include "dreaming.h" using namespace std; #define ll long long const int mxN = 1e5 + 100; const int INF = 1e18; vector<pair<ll, ll>> adj[mxN]; ll down_dp[mxN], up_dp[mxN]; bool vis[mxN]; ll cmax = 0, cost = 0; void dfs(ll u, ll p){ vis[u] = 1; // cout << u << " "; for(auto it : adj[u]){ if(it.first ^ p){ dfs(it.first, u); down_dp[u] = max(down_dp[u], down_dp[it.first] + it.second); } } } void reroot(ll u, ll p){ pair<ll, ll> mx1, mx2; mx1.first = mx2.first = mx2.second = -1; for(auto it : adj[u]){ if(it.first ^ p){ if(mx1.first == -1){ mx1.first = it.first; mx1.second = down_dp[it.first] + it.second; }else if((down_dp[it.first] + it.second) >= mx1.second){ swap(mx1, mx2); mx1.first = it.first; mx1.second = down_dp[it.first] + it.second; }else if((down_dp[it.first] + it.second) > mx2.second){ mx2.first = it.first; mx2.second = down_dp[it.first] + it.second; } } } for(auto it : adj[u]){ if(it.first ^ p){ if(it.first == mx1.first){ if(mx2.first != -1){ up_dp[it.first] = mx2.second + it.second; } }else if(mx1.first != -1){ up_dp[it.first] = mx1.second + it.second; } up_dp[it.first] = max(up_dp[it.first], up_dp[u] + it.second); reroot(it.first, u); } } cmax = min(cmax, max(up_dp[u], down_dp[u])); cost = max({up_dp[u], down_dp[u], cost}); } int travelTime(int N,int M,int L,int A[],int B[],int T[]){ for(int i=0;i<M;++i){ adj[A[i]].push_back({B[i],T[i]}); adj[B[i]].push_back({A[i],T[i]}); } vector<ll> tokens; for(int i = 0; i < N; ++i){ if(!vis[i]){ cmax = INF; // cout << "started visiting:- "; dfs(i, -1); reroot(i, -1); // cout << "ended visiting\n"; tokens.push_back(cmax); // cout << i << " " << cmax << endl; } } sort(tokens.begin(), tokens.end()); // cout << "2 updp : " << up_dp[2] << " downdp: " << down_dp[2] << endl; if(tokens.size() == 1){ return (int) max(cost, tokens.back()); }else{ return (int) max(cost, tokens[tokens.size() - 2] + L + tokens.back()); } }

Compilation message (stderr)

dreaming.cpp:8:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    8 | const int INF = 1e18;
      |                 ^~~~
#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...