oj.uz

Submission #525739

# Submission time Handle Problem Language Result Execution time Memory
525739 2022-02-12T17:56:44 Z Urvuk3 Dreaming (IOI13_dreaming) C++17
18 / 100
 373 ms 34160 KB 
#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),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)> propagate=[&](int node,int prev){
        ll mx=0;
        int idx=0;
        for(int i=0;i<sz(adj[node]);i++){
            int v=adj[node][i];
            if(v==prev) continue;
            if(idx!=0) nadstablo_udaljenost[v]=max(nadstablo_udaljenost[v],mx+edge[{node,v}]);
            int tmp_val=podstablo_udaljenost1[v]+edge[{v,node}];
            if(mx<tmp_val){
                mx=tmp_val;
            }
            idx++;
        }
        for(int i=sz(adj[node])-1;i>=0;i--){
            int v=adj[node][i];
            if(v==prev) continue;
            if(idx!=0) nadstablo_udaljenost[v]=max(nadstablo_udaljenost[v],mx+edge[{node,v}]);
            int tmp_val=podstablo_udaljenost1[v]+edge[{v,node}];
            if(mx<tmp_val){
                mx=tmp_val;
            }
            idx++;
        }
    };

    function<void(int,int)> dfs2=[&](int node,int prev){
        propagate(node,prev);
        if(prev!=-1){
            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<<"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.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 34160 KB Output is correct
2 Correct 359 ms 33328 KB Output is correct
3 Correct 203 ms 26112 KB Output is correct
4 Correct 31 ms 5196 KB Output is correct
5 Correct 24 ms 3852 KB Output is correct
6 Correct 54 ms 7736 KB Output is correct
7 Incorrect 1 ms 332 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 34160 KB Output is correct
2 Correct 359 ms 33328 KB Output is correct
3 Correct 203 ms 26112 KB Output is correct
4 Correct 31 ms 5196 KB Output is correct
5 Correct 24 ms 3852 KB Output is correct
6 Correct 54 ms 7736 KB Output is correct
7 Incorrect 1 ms 332 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 26844 KB Output is correct
2 Correct 226 ms 26912 KB Output is correct
3 Correct 195 ms 26744 KB Output is correct
4 Correct 196 ms 26944 KB Output is correct
5 Correct 196 ms 26676 KB Output is correct
6 Correct 210 ms 29120 KB Output is correct
7 Correct 203 ms 28068 KB Output is correct
8 Correct 187 ms 26300 KB Output is correct
9 Correct 191 ms 26232 KB Output is correct
10 Correct 202 ms 27796 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 88 ms 30384 KB Output is correct
13 Correct 91 ms 30392 KB Output is correct
14 Correct 95 ms 30400 KB Output is correct
15 Correct 89 ms 30368 KB Output is correct
16 Correct 89 ms 30392 KB Output is correct
17 Correct 93 ms 30380 KB Output is correct
18 Correct 89 ms 30332 KB Output is correct
19 Correct 93 ms 30440 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 3 ms 1228 KB Output is correct
23 Correct 88 ms 30396 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 34160 KB Output is correct
2 Correct 359 ms 33328 KB Output is correct
3 Correct 203 ms 26112 KB Output is correct
4 Correct 31 ms 5196 KB Output is correct
5 Correct 24 ms 3852 KB Output is correct
6 Correct 54 ms 7736 KB Output is correct
7 Incorrect 1 ms 332 KB Output isn't correct
8 Halted 0 ms 0 KB -