Submission #525662

#	Time	Username	Problem	Language	Result	Execution time	Memory
525662		Urvuk3	Dreaming (IOI13_dreaming)	C++17	0 / 100	214 ms	35392 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),podstablo_udaljenost1(N+1),podstablo_udaljenost2(N+1);
    vector<ll> udaljenost(N+1),dubina(N+1);

    function<void(int,int)> dfs1=[&](int node,int prev){
        podstablo_udaljenost1[node]=0; podstablo_udaljenost2[node]=0;
        if(prev!=-1) dubina[node]=dubina[prev]+1;
        else dubina[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)> dfs2=[&](int node,int prev){
        nadstablo_udaljenost[node]=0;
        if(prev!=-1){
            nadstablo_udaljenost[node]=nadstablo_udaljenost[prev]+edge[{prev,node}];
        }
        for(auto v:adj[prev]){
            if(dubina[v]>dubina[prev] && v!=node){
                nadstablo_udaljenost[node]=max(nadstablo_udaljenost[node],podstablo_udaljenost1[v]+edge[{v,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 node=0;
        ll val=LINF;
        for(auto v:trees[i]){
            if(udaljenost[v]<=val){
                val=udaljenost[v]; node=v;
            }
        }
        all_trees.pb({val,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<<"dubina["<<v<<"]="<<dubina[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: 0 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23