Submission #526103

#	Time	Username	Problem	Language	Result	Execution time	Memory
526103		Urvuk3	Dreaming (IOI13_dreaming)	C++17	100 / 100	519 ms	47184 KiB

dreaming

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

using namespace std;

#define ll long long
const ll INF=1e9,LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define PRINT(x) cerr<<#x<<'='<<x<<endl;
#define pb push_back
#define PRINTvec(arr) { cerr<<#arr<<"="; for(auto h:arr) cerr<<h<<" "; cerr<<endl; }

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    vector<int> adj[N+1];
    map<pair<int,int>,ll> edge;
    for(int i=0;i<M;i++){
        int u=A[i],v=B[i],w=T[i];
        u++; v++;
        adj[u].pb(v);
        adj[v].pb(u);
        edge[{u,v}]=w;
        edge[{v,u}]=w;
    }
    vector<int> trees[N+1];
    vector<bool> vis(N+1,false);
    int idx=1;
    function<void(int,int)> dfs=[&](int node,int prev){
        vis[node]=true;
        trees[idx].pb(node);
        for(auto v:adj[node]) if(v!=prev) dfs(v,node);
    };

    for(int i=1;i<=N;i++){
        if(!vis[i]){
            dfs(i,-1);
            idx++;
        }
    }
    vector<ll> nadstablo_udaljenost(N+1,0),podstablo_udaljenost1(N+1),podstablo_udaljenost2(N+1);
    vector<ll> udaljenost(N+1);

    function<void(int,int)> dfs1=[&](int node,int prev){
        podstablo_udaljenost1[node]=0; podstablo_udaljenost2[node]=0;
        vector<ll> tmp; tmp.pb(0); tmp.pb(0);
        for(auto v:adj[node]){
            if(v!=prev){
                dfs1(v,node);
                tmp.pb(podstablo_udaljenost1[v]+edge[{node,v}]);
            }
        }
        sort(all(tmp),greater<int>());
        podstablo_udaljenost1[node]=tmp[0]; podstablo_udaljenost2[node]=tmp[1];
    };

    function<void(int,int)> propagate=[&](int node,int prev){
        //cout<<"propagiranje:"<<endl;
        //PRINT(node); PRINT(prev);
        ll mx=0;
        int idx=0;
        for(int i=0;i<sz(adj[node]);i++){
            int v=adj[node][i];
            //PRINT(v);
            if(v==prev) continue;
            //PRINT(mx);
            //cout<<"edge[{"<<node<<","<<v<<"}]="<<edge[{node,v}]<<endl;
            if(idx!=0) nadstablo_udaljenost[v]=max(nadstablo_udaljenost[v],mx+edge[{node,v}]);
            //cout<<"nadstablo_udaljenost["<<v<<"]="<<nadstablo_udaljenost[v]<<endl;
            int tmp_val=podstablo_udaljenost1[v]+edge[{v,node}];
            //PRINT(tmp_val);
            if(mx<tmp_val){
                mx=tmp_val;
            }
            idx++;
        }
        //cout<<endl;
        mx=0;
        idx=0;
        for(int i=sz(adj[node])-1;i>=0;i--){
            int v=adj[node][i];
            //PRINT(v);
            //PRINT(mx);
            if(v==prev) continue;
            if(idx!=0) nadstablo_udaljenost[v]=max(nadstablo_udaljenost[v],mx+edge[{node,v}]);
            //cout<<"nadstablo_udaljenost["<<v<<"]="<<nadstablo_udaljenost[v]<<endl;
            int tmp_val=podstablo_udaljenost1[v]+edge[{v,node}];
            //PRINT(tmp_val);
            if(mx<tmp_val){
                mx=tmp_val;
            }
            idx++;
        } //cout<<endl;
    };

    function<void(int,int)> dfs2=[&](int node,int prev){
        propagate(node,prev);
        //PRINT(node);
        //cout<<"nadstablo_udaljenost["<<node<<"]="<<nadstablo_udaljenost[node]<<endl; cout<<endl;
        if(prev!=-1){
            nadstablo_udaljenost[node]=max(nadstablo_udaljenost[node],nadstablo_udaljenost[prev]+edge[{prev,node}]);
        }
        for(auto v:adj[node]) if(v!=prev) dfs2(v,node);
        udaljenost[node]=max(nadstablo_udaljenost[node],podstablo_udaljenost1[node]);
    };

    vector<pii> all_trees;

    for(int i=1;i<idx;i++){
        int root=trees[i][0];
        dfs1(root,-1);
        dfs2(root,-1);
        int tmp_node=0;
        ll tmp_val=LINF;
        for(auto v:trees[i]){
            if(udaljenost[v]<=tmp_val){
                tmp_val=udaljenost[v]; tmp_node=v;
            }
        }
        all_trees.pb({tmp_val,tmp_node});
    }

    sort(all(all_trees),greater<pair<ll,ll>>());

    for(int i=1;i<sz(all_trees);i++){
        int node=all_trees[i].se;
        int first=all_trees[0].se;
        adj[node].pb(first); adj[first].pb(node);
        edge[{node,first}]=L; edge[{first,node}]=L;
    }

    /*
    int node=0; ll val=LINF;
    for(int i=1;i<idx;i++){
        int root=trees[i][0];
        dfs1(root,-1);
        dfs2(root,-1);
        if(i==1){
            for(auto v:trees[i]){
                if(udaljenost[v]<=val){
                    val=udaljenost[v]; node=v;
                }
            }
        }
        else{
            int tmp_node=0,tmp_val=INF;
            for(auto v:trees[i]){
                if(udaljenost[v]<=tmp_val){
                    tmp_val=udaljenost[v]; tmp_node=v;
                }
            }
            adj[tmp_node].pb(node); adj[node].pb(tmp_node);
            edge[{tmp_node,node}]=L; edge[{node,tmp_node}]=L;
        }
    }
    */

    /*
    for(int i=1;i<idx;i++){
        PRINTvec(trees[i]);
        for(auto v:trees[i]){
            cout<<"nadstablo_udaljenost["<<v<<"]="<<nadstablo_udaljenost[v]<<endl;
            cout<<"podstablo_udaljenost1["<<v<<"]="<<podstablo_udaljenost1[v]<<endl;
            cout<<"podstablo_udaljenost2["<<v<<"]="<<podstablo_udaljenost2[v]<<endl;
            cout<<"udaljenost["<<v<<"]="<<udaljenost[v]<<endl;
            cout<<endl;
        }
        cout<<endl<<endl;
    }
    */

    dfs1(1,-1);
    ll diametar=0;
    for(int node=1;node<=N;node++){
        diametar=max(diametar,podstablo_udaljenost1[node]+podstablo_udaljenost2[node]);
    }
    return diametar;
}

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