oj.uz

Submission #1007188

# Submission time Handle Problem Language Result Execution time Memory
1007188 2024-06-24T12:58:00 Z Mardonbekhazratov Dreaming (IOI13_dreaming) C++17
0 / 100
 26 ms 9808 KB 
#include "dreaming.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long

int n,m,l;
vector<int>sz;
vector<bool>vis;
vector<vector<pair<int,int>>>v;

int dfs(int x){
    sz[x]=0;
    vis[x]=true;
    for(auto [z,w]:v[x]){
        if(!vis[z]){
            sz[x]+=w+dfs(z);
        }
    }
    return sz[x];
}

int mn;

void dfs2(int x,int dis){
    vis[x]=true;
    int mx=0;
    for(auto [z,w]:v[x]){
        if(!vis[z]){
            mx=max(mx,sz[z]+w);
            dfs2(z,dis);
        }
    }
    mn=min(mn,max(mx,dis-sz[x]));
}

void dfs3(int x,int dis,int p=-1){
    vector<int>a;
    for(auto [z,w]:v[x]){
        if(z!=p){
            a.push_back(sz[z]+w);
            dfs3(z,dis,x);
        }
    }
    a.push_back(dis-sz[x]);
    sort(a.begin(),a.end());
    int s=a.back();
    a.pop_back();
    if(a.size()) s+=a.back();
    mn=max(mn,s);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n=N;
    m=M;
    l=L;
    v.assign(n,{});
    for(int i=0;i<m;i++){
        v[A[i]].push_back({B[i],T[i]});
        v[B[i]].push_back({A[i],T[i]});
    }
    sz.resize(n);
    vis.assign(n,false);
    for(int i=0;i<n;i++){
        if(!vis[i]){
            dfs(i);
        }
    }
    vis.assign(n,false);
    vector<int>a;
    for(int i=0;i<n;i++){
        if(!vis[i]){
            mn=(int)1e9;
            dfs2(i,sz[i]);
            a.push_back(mn);
        }
    }
    if(a.size()==1){
        mn=0;
        dfs3(0,sz[0]);
        return mn;
    }
    sort(a.begin(),a.end());
    //for(int x:a) cout<<x<<' ';
    return a[a.size()-1]+a[a.size()-2]+l;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 9808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 9808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 9808 KB Output isn't correct
2 Halted 0 ms 0 KB -