oj.uz

Submission #1029922

# Submission time Handle Problem Language Result Execution time Memory
1029922 2024-07-21T13:53:50 Z vjudge1 Dreaming (IOI13_dreaming) C++17
0 / 100
 43 ms 19916 KB 
#include "dreaming.h"

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
using pii=pair<int,int>;

const int lim=1e5+100;


int n,m;
int ans=0;
vector<pii>v[lim];
vector<int>results,curnodes;
bool done[lim];
int dist[lim],dp[lim],up[lim];

void dd(int node,int par,bool init){
    if(init)curnodes.pb(node);
    for(auto[j,c]:v[node]){
        if(j!=par){
            dist[j]=dist[node]+c;
            dd(j,node,init);
        }
    }
}

pair<pii,pii>bests[lim];

void ins(pair<pii,pii>&p,pii to){
    if(p.first.first<to.first)swap(to,p.first);
    if(p.second.first<to.first)p.second=to;
}

int dfs(int node,int par){
    dp[node]=0;
    for(auto[j,c]:v[node]){
        if(j==par)continue;
        dp[node]=max(dp[node],dfs(j,node)+c);
        ins(bests[node],{dp[j]+c,j});
    }
    return dp[node];
}

void dfs1(int node,int par){
    ins(bests[node],{up[node],-1});
    for(auto[j,c]:v[node]){
        if(j==par)continue;
        if(j^bests[node].first.second){
            up[j]=bests[node].first.first+c;
        }else{
            up[j]=bests[node].second.first+c;
        }
        dfs1(j,node);
    }
}


void process(int root){
    curnodes.clear();
    dist[root]=0;
    dd(root,-1,1);
    for(int i:curnodes){
        done[i]=1;
        if(dist[root]<dist[i]){
            root=i;
        }
    }
    if(!dist[root]){
        results.pb(0);
        return;
    }
    dist[root]=0;
    dd(root,-1,0);
    for(int i:curnodes){
        ans=max(ans,i);
    }
    dfs(root,-1);
    up[root]=0;
    dfs1(root,-1);
    int topush=INT_MAX;
    for(int i:curnodes){
        topush=min(topush,max({dp[i],up[i]}));
    }
    results.pb(topush);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    ans=0;
    n=N;
    m=M;
    results.clear();
    for(int i=0;i<n;i++){
        v[i].clear();
        done[i]=0;
        dist[i]=INT_MAX;
    }
    for(int i=0;i<m;i++){
        v[A[i]].pb({B[i],T[i]});
        v[B[i]].pb({A[i],T[i]});
    }
    for(int i=0;i<n;i++){
        if(!done[i]){
            process(i);
        }
    }
    sort(results.begin(),results.end());
    if(results.size()==2){
        ans=max(ans,results[0]+results[1]+L);
    }
    if(2<results.size()){
        ans=max(ans,results[results.size()-1]+results[results.size()-2]+L);
        ans=max(ans,results[results.size()-3]+results[results.size()-2]+2*L);
    }
    return ans;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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