Submission #1267156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267156		lambiguinho	Dreaming (IOI13_dreaming)	C++20	18 / 100	38 ms	18500 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
pair<int,int> dfs(int a, int ant, int d, vector<vector<pair<int,int>>>& v, vector<pair<int,int>>& pais, vector<bool>& vis) {
    pair<int,int> resp = {d,a};
    pais[a] = {d,ant};
    vis[a] = 1;
    for (auto [c,b] : v[a]) {
        if (b != ant) {
            resp = max(resp,dfs(b,a,d+c,v,pais,vis));
        }
    }
    return resp;
}

pair<int,int> centro(int a, int b, int d, vector<pair<int,int>>& pais) {
    int val = d;
    while (pais[a].first > d/2) {
        val = pais[a].first;
        a = pais[a].second;
    }
    return {d,max(val,pais[a].first)};
}

int travelTime(int n, int m, int l, int inp1[], int inp2[], int inpval[]) {
    vector<vector<pair<int,int>>> v(n);
    vector<pair<int,int>> pais(n,{0,-1});
    vector<bool> vis(n,0);
    for (int i = 0; i < m; i++) {
        int a = inp1[i], b = inp2[i], c = inpval[i];
        v[a].push_back({c,b});
        v[b].push_back({c,a});
    }
    vector<pair<int,int>> diam;
    int resp = 0, len = 0;
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            len++;
            auto [_,a] = dfs(i,-1,0,v,pais,vis);
            auto [d,b] = dfs(a,-1,0,v,pais,vis);
            diam.push_back(centro(b,a,d,pais));
            resp = max(resp,diam[len-1].first);
        }
    }
    sort(diam.begin(),diam.end());
    if (len > 2) {
        resp = max(resp,diam[len-2].second + diam[len-3].second + 2*l);
    }
    if (len > 1) {
        resp = max(resp, diam[len-1].second + diam[len-2].second + l);
    }
    return resp;
}

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