Submission #452148

#	Time	Username	Problem	Language	Result	Execution time	Memory
452148		FEDIKUS	Dreaming (IOI13_dreaming)	C++17	100 / 100	128 ms	18756 KiB

dreaming

#include "dreaming.h"

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define xx first
#define yy second

using namespace std;

typedef pair<int,int> pii;

const int maxn=1e5+10;

bool bio[maxn];
int dist[maxn];
int dp[maxn];
vector<pii> g[maxn];

void dfs1(int cvor){
    if(bio[cvor]) return;
    bio[cvor]=true;
    dp[cvor]=0;
    for(pii i:g[cvor]){
        if(bio[i.xx]) continue;
        dfs1(i.xx);
        dp[cvor]=max(dp[cvor],dp[i.xx]+i.yy);
    }
}

pii dfs2(int cvor,int prosli){
    pii ret={dp[cvor],cvor};
    int maxi=0;
    int maxi2=0;
    for(pii i:g[cvor]){
        if(dp[i.xx]+i.yy>=maxi){
            maxi2=maxi;
            maxi=dp[i.xx]+i.yy;
        }else if(dp[i.xx]+i.yy>maxi2){
            maxi2=dp[i.xx]+i.yy;
        }
    }
    for(pii i:g[cvor]){
        if(i.xx==prosli) continue;
        int bc=dp[cvor];
        int bi=dp[i.xx];
        int vr=dp[i.xx]+i.yy;
        if(vr==maxi) dp[cvor]=maxi2;
        dp[i.xx]=max(dp[i.xx],dp[cvor]+i.yy);
        ret=min(ret,dfs2(i.xx,cvor));
        dp[cvor]=bc;
        dp[i.xx]=bi;
    }
    return ret;
}

pii najd(int cvor,int prosli){
    pii ret=mp(0,cvor);
    for(pii i:g[cvor]){
        if(i.xx==prosli) continue;
        pii pom=najd(i.xx,cvor);
        pom.xx+=i.yy;
        ret=max(ret,pom);
    }
    return ret;
}

int odg(int cvor){
    return najd(najd(cvor,-1).yy,-1).xx;
}

int travelTime(int n,int m,int l,int a[],int b[],int t[]) {
    for(int i=0;i<n;i++) dist[i]=-1;
    for(int i=0;i<m;i++){
        g[a[i]].pb(mp(b[i],t[i]));
        g[b[i]].pb(mp(a[i],t[i]));
    }
    vector<pii> kurac;
    for(int i=0;i<n;i++){
        if(bio[i]) continue;
        dfs1(i);
        kurac.pb(dfs2(i,-1));
    }
    sort(kurac.begin(),kurac.end(),greater<pii>());
    for(int i=1;i<kurac.size();i++){
        g[kurac[0].yy].pb(mp(kurac[i].yy,l));
        g[kurac[i].yy].pb(mp(kurac[0].yy,l));
    }
    return odg(0);
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int i=1;i<kurac.size();i++){
      |                 ~^~~~~~~~~~~~~

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