Submission #1180176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180176		tapilyoca	꿈 (IOI13_dreaming)	C++20	100 / 100	405 ms	25868 KiB

dreaming

/***********************************************
* auth: tapilyoca                              *
* date: 04/07/2025 at 08:59:48                 *
* dots: https://github.com/tapilyoca/dotilyoca * 
***********************************************/

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

using namespace std;
const long long MOD = 1e9+7;

// using ll = long long;
using ll = int;
using vll = vector<ll>;
using pll = pair<ll,ll>;
using str = string;
#define dbg(x) cerr << #x << ": " << x << endl;

/***********************************************/


pll getDiameter(ll &N, int at, vector<vector<pll>> &adj, vector<bool> &gvis){

    // vll dists(N+1,0);
    map<ll,ll> dists;
    dists[at] = 0;

    queue<ll> q;
    q.push(at);    

    // vector<bool> vis(N+1,0);
    map<ll,bool> vis;

    ll mx = 0;
    ll mxnode = at;

    vis[at] = 1;

    while(!q.empty()){
        ll curr = q.front();
        q.pop();

        for(pll p : adj[curr]){
            ll v = p.first;

            if(vis[v]) continue;

            vis[v] = 1;
            gvis[v] = 1;
            q.push(v);
            dists[v] = dists[curr] + p.second;

            if(dists[v] > mx){
                mx = dists[v];
                mxnode = v;
            }
        }
    }

    if(vis.size() == 1){
        return {0,at};
    }

    vis.clear();
    dists.clear();

    // for(auto itr = dists.begin(); itr != dists.end(); itr++){
    //     cerr << itr->first << " " << itr->second << endl;
    // }
    
    q.push(mxnode);
    dists[mxnode] = 0;
    vis[mxnode] = 1;

    ll out = 0;

    ll root = 0;

    while(!q.empty()){
        ll curr = q.front();
        q.pop();

        for(pll p : adj[curr]){
            ll v = p.first;
            if(vis[v]) continue;
            vis[v] = 1;
            q.push(v);
            dists[v] = dists[curr] + p.second;

            if(dists[v] > out){
                out = dists[v];
                root = v;
            }
        }
    }

    // now to get radius
    // want path on the diameter
    // root at stuff
    map<ll,ll> parent;
    map<ll,ll> child;

    q.push(root);
    parent[root] = root;

    while(!q.empty()){
        ll curr = q.front();
        q.pop();
        for(pll p : adj[curr]){
            ll v = p.first;
            if(v == parent[curr]) continue;

            parent[v] = curr;
            child[curr] = v;
            q.push(v);        
        }
    }

    if(parent[mxnode] == root or parent[mxnode] == mxnode){
        return {out,root};
    }

    ll radius = out;
    ll radiusnode = mxnode;

    for(ll curr = mxnode; curr != parent[curr]; curr = parent[curr]){
        // dbg(dists[curr]);
        // dbg(float(out/2));
        if(abs(dists[curr] - out/2.0) < radius){
            radius = ceil(abs(dists[curr] - out/2.0));
            radiusnode = curr;
        }
    }


    // dbg(root);
    // dbg(mxnode);

    // dbg(dists[radiusnode]);
    // dbg(dists[mxnode]);
    // dbg(dists[root] - dists[radiusnode]);

    return{max(dists[radiusnode], dists[root] - dists[radiusnode]),radiusnode};
}

ll travelTime(ll N, ll M, ll L, ll A[], ll B[], ll T[]){
    vector<vector<pll>> adj(N+1);
    
    for(int i = 0; i < M; i++){
        adj[B[i]].push_back({A[i],T[i]});
        adj[A[i]].push_back({B[i],T[i]});
    }

    ll compCount = (N-1)-M+1;


    vector<ll> diameters(compCount+10,0);
    vector<ll> radii(compCount+10,0);
    
    vector<bool> vis(N+1,0);

    ll currComp = -1;

    ll mxWeight = 0;
    ll mxInQuestion = 0;

    for(int i = 0; i < N; i++){
        if(vis[i]) continue;
        vis[i] = 1;
        currComp++;

        pair<ll,ll> temp = getDiameter(N,i,adj,vis);
        radii[currComp] = temp.second; // poorly named, this is the node
        diameters[currComp] = temp.first; // poorly named, this is the radius
        
        if(diameters[currComp] > mxWeight){
            mxWeight = diameters[currComp];
            mxInQuestion = radii[currComp];
        }

        // cerr << "CENTER OF " << currComp << " IS " << radii[currComp] << " WITH " << diameters[currComp] << endl;
    }

    // cerr << "HEAVIEST IS " << mxInQuestion << " WITH " << mxWeight << endl;

    for(int i = 0; i < compCount; i++){
        if(radii[i] == mxInQuestion) continue;
        adj[radii[i]].push_back({mxInQuestion,L});
        adj[mxInQuestion].push_back({radii[i],L});

        // cerr << "ADDED FROM " << radii[i] << " TO " << mxInQuestion << endl;
    }


    // final diameter search
    
    vis.assign(N+1,0);

    vll dists(N+1,0);
    
    queue<ll> q;
    q.push(0);
    vis[0] = 1;

    ll mxnode = 0;
    ll mxdist = 0;

    while(!q.empty()){
        ll curr = q.front();
        q.pop();
        for(pll tmp : adj[curr]){
            ll v = tmp.first;
            if(vis[v]) continue;
            vis[v] = 1;
            q.push(v);

            dists[v] = dists[curr] + tmp.second;
            if(dists[v] > mxdist){
                mxdist = dists[v];
                mxnode = v;
            }
        }
    }

    // dbg(mxnode);

    vis.assign(N+1,0);
    vis[mxnode] = 1;
    ll diameter = 0;
    dists.assign(N+1,0);

    q.push(mxnode);
    while(!q.empty()){
        ll curr = q.front();
        q.pop();
        for(pll tmp : adj[curr]){
            ll v = tmp.first;
            if(vis[v]) continue;
            vis[v] = 1;
            q.push(v);

            dists[v] = dists[curr] + tmp.second;
            if(dists[v] > diameter){
                diameter = dists[v];
            }
        }
    }

    return diameter;
}

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