Submission #485627

#	Time	Username	Problem	Language	Result	Execution time	Memory
485627		Joo	Dreaming (IOI13_dreaming)	C++17	100 / 100	95 ms	18316 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

const int MXN = 1e5+10;
using pi = pair<int,int>;

int best,mx[MXN][2],dps[MXN],dpp[MXN],fr[MXN],pos;
bool vi[MXN];
vector<pi> G[MXN];

void dfs1(int u, int p){
    vi[u] = true;
    for(auto [v, w] : G[u]){
        if(v == p) continue;
        dfs1(v, u);
        dps[u] = max(dps[u], dps[v]+w);

        int tmp = dps[v]+w, node = v;
        if(tmp > mx[u][0]){
            swap(tmp, mx[u][0]);
            swap(fr[u], node);
        }
        if(tmp > mx[u][1]){
            swap(tmp, mx[u][1]);
        }
    }
}

void dfs2(int u, int p, int code = 0){
    if(code){
        best = max(best, dps[u]+dpp[u]);
    }else{
        if(max(dps[u], dpp[u]) < best){
            best = max(dps[u], dpp[u]);
            pos = u;
        }
    }
    for(auto [v, w] : G[u]){
        if(v == p) continue;

        if(v != fr[u]){
            dpp[v] = max(dpp[u], mx[u][0])+w;
        }else{
            dpp[v] = max(dpp[u], mx[u][1])+w;
        }

        dfs2(v, u, code);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]){
    for(int i = 0; i < M; i++){
        G[A[i]+1].emplace_back(B[i]+1, T[i]);
        G[B[i]+1].emplace_back(A[i]+1, T[i]);
    }

    vector<pi> res;
    for(int i = 1; i <= N; i++){
        if(!vi[i]){
            best = 2e9, pos = -1;
            dfs1(i, 0);
            dfs2(i, 0);
            res.emplace_back(best, pos);
        }
    }

    sort(res.rbegin(), res.rend());
    /*for(auto [val, idx] : res){
        cout << val << " " << idx << "\n";
    }*/
    for(int i = 1; i < res.size(); i++){
        G[res[i].second].emplace_back(res[0].second, L);
        G[res[0].second].emplace_back(res[i].second, L);
    }

    for(int i = 0; i <= N; i++){
        mx[i][0] = mx[i][1] = dps[i] = dpp[i] = fr[i] = 0;
    }

    best = 0;
    dfs1(1, 0);
    dfs2(1, 0, 1);

    return best;
}
/*
int main(void){
    int N,M,L;
    cin >> N >> M >> L;
    int A[M], B[M], T[M];
    for(int i = 0; i < M; i++){
        cin >> A[i];
    }
    for(int i = 0; i < M; i++){
        cin >> B[i];
    }
    for(int i = 0; i < M; i++){
        cin >> T[i];
    }
    cout << travelTime(N, M, L, A, B, T) << "\n";
    return 0;
}*/

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:72:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int i = 1; i < res.size(); i++){
      |                    ~~^~~~~~~~~~~~

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