Submission #1161936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161936		ty_mxzhn	Dreaming (IOI13_dreaming)	C++20	100 / 100	191 ms	22972 KiB

dreaming

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

using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    // cout << "input : " << N << " " << M << " " << L << endl;
    // for(int i = 0;i<M;i++){
    //     cout << "edge : " << A[i] << " " << B[i] << " " << T[i] << endl;
    // }
    vector < pair < int , int > > tree[N];
    int vis[N] = {0};
    for(int i = 0;i<M;i++){
        tree[A[i]].push_back({B[i] , T[i]});
        tree[B[i]].push_back({A[i] , T[i]});
    }
    // cout << "done1" << endl;
    vector < int > vec;
    int maxi = 0;
    for(int i = 0;i<N;i++){
        if(vis[i] == 0){
            // cout << "starting at : " << i << endl;
            auto furthest = [&](int st){
                map < int , int > visited;
                priority_queue < pair < int , int > > pq;
                pq.push({0,st});
                pair < int , int > ret = {0,st};
                while(!pq.empty()){
                    auto tmp = pq.top();
                    pq.pop();
                    if(visited[tmp.second])continue;
                    vis[tmp.second] = 1;
                    // cout << "visited : " << tmp.first << " " << tmp.second << endl;
                    visited[tmp.second] = 1;
                    ret = max(ret , {-tmp.first , tmp.second});
                    for(auto itr : tree[tmp.second]){
                        // cout << "pushing : " << tmp.first - itr.second << " , " << itr.first << endl;
                        pq.push({tmp.first - itr.second , itr.first});
                    }
                }
                return ret.second;
            };
            int node1 = furthest(i);
            // cout << "NODE1 : " << node1 << endl;
            int node2 = furthest(node1);
            // cout << "NODE2 : " << node2 << endl;
            // cout << "done3" << endl;
            vector < int > path;
            function<bool(int,int,int)> dfs = [&](int node , int par , int parcost){
                // cout << "dfs : " << node << " " << par << " " << parcost << endl;
                if(node == node2){
                    path.push_back(parcost);
                    return true;
                }
                bool bl = 0;
                for(auto itr : tree[node]){
                    if(itr.first == par)continue;
                    // cout << node << " -> " << itr.first << endl;
                    if(dfs(itr.first,node,itr.second)){
                        path.push_back(parcost);
                        bl = 1;
                    }
                }
                return bl;
            };
            dfs(node1,node1,0);
            // cout << "path : ";for(auto itr : path)cout << itr << " ";cout << endl;
            // cout << "done4" << endl;
            int sum = accumulate(all(path) , 0ll) , cursum = 0 , locans = sum;
            maxi = max(maxi , sum);
            for(int i = 0;i<sz(path);i++){
                cursum += path[i];
                locans = min(locans , max(cursum , sum-cursum));
            }
            // cout << "locans : " << locans << endl;
            vec.push_back(locans);
        }
    }
    sort(all(vec) , greater < int >{});
    if(sz(vec) == 1)return max(maxi , vec[0]);
    else if(sz(vec) == 2)return max(maxi , vec[0] + vec[1] + L);
    else return max({maxi , vec[0] + vec[1] + L , vec[1] + vec[2] + 2 * L});
}

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