Submission #430695

#	Time	Username	Problem	Language	Result	Execution time	Memory
430695		muhammad_hokimiyon	Dreaming (IOI13_dreaming)	C++14	100 / 100	177 ms	17140 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>

#define fi first
#define se second
#define ll long long
#define dl double

using namespace std;

const int maxN = 1e5 + 7;

int val,vv,ve;
int d[maxN];
int u[maxN];
bool used[maxN];
vector<pair<int, int>> v[maxN];

void dfs1(int x, int p)
{
        used[x] = true;
        for(auto y : v[x]){
                if(y.fi == p)continue;
                dfs1(y.fi, x);
                d[x] = max(d[x], d[y.fi] + y.se);
        }
}

void dfs2(int x, int p)
{
        int mx1 = -1, mx2 = -1;
        int v1 = -1, v2 = -1;
        for(auto y : v[x]){
                if(y.fi == p)continue;
                if(d[y.fi] + y.se > mx1){
                        if(mx1 > mx2){
                                mx2 = mx1;
                                v2 = v1;
                        }
                        mx1 = d[y.fi] + y.se;
                        v1 = y.fi;
                }else if(d[y.fi] + y.se > mx2){
                        mx2 = d[y.fi] + y.se;
                        v2 = y.fi;
                }
        }
        if(max(u[x], d[x]) < val){
                vv = x;
        }
        val = min(val, max(u[x], d[x]));
        for(auto y : v[x]){
                if(y.fi == p)continue;
                u[y.fi] = max(u[y.fi], u[x] + y.se);
                if(y.fi != v1)u[y.fi] = max(u[y.fi], mx1 + y.se);
                else if(mx2 != -1){
                        u[y.fi] = max(u[y.fi], mx2 + y.se);
                }
                dfs2(y.fi, x);
        }
}

void dfs(int x, int p, int sum)
{
        used[x] = true;
        if(sum >= val){
                val = sum;
                ve = x;
        }
        for(auto y : v[x]){
                if(y.first != p){
                        dfs(y.first, x, sum + y.second);
                }
        }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
        for(int i = 0; i < M; i++){
                v[A[i]].push_back({B[i], T[i]});
                v[B[i]].push_back({A[i], T[i]});
        }
        vector<pair<int, int>> X;
        for(int i = 0; i < N; i++){
                if(!used[i]){
                        val = 1e9;
                        dfs1(i, i);
                        dfs2(i, i);
                        X.push_back({val, vv});
                }
        }
        sort(X.rbegin(), X.rend());
        for(int i = 1; i < (int)X.size(); i++){
                v[X[0].second].push_back({X[i].second, L});
                v[X[i].second].push_back({X[0].second, L});
        }
        val = ve = 0;
        dfs(0, 0, 0);
        val = 0;
        dfs(ve, ve, 0);
        return val;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:32:22: warning: variable 'v2' set but not used [-Wunused-but-set-variable]
   32 |         int v1 = -1, v2 = -1;
      |                      ^~

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