Submission #1243834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243834		rayan_bd	Dreaming (IOI13_dreaming)	C++20	14 / 100	38 ms	14144 KiB

dreaming

#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;
      |                 ^~~~

• Subtask 1: 14 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23