Submission #452146

#	Time	Username	Problem	Language	Result	Execution time	Memory
452146		FEDIKUS	Dreaming (IOI13_dreaming)	C++17	77 / 100	1053 ms	14060 KiB

dreaming

#pragma GCC optimize("Ofast")
#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);
    }
}

void uradi(int cvor,int prosli){
    dp[prosli]=dp[cvor]=0;
    for(auto i:g[prosli]){
        if(i.xx==cvor) continue;
        dp[prosli]=max(dp[prosli],dp[i.xx]+i.yy);
    }
    for(auto i:g[cvor]){
        dp[cvor]=max(dp[cvor],dp[i.xx]+i.yy);
    }
}

pii dfs2(int cvor,int prosli){
    if(prosli!=-1) uradi(cvor,prosli);
    pii ret={dp[cvor],cvor};
    for(pii i:g[cvor]){
        if(i.xx==prosli) continue;
        ret=min(ret,dfs2(i.xx,cvor));
    }
    if(prosli!=-1) uradi(prosli,cvor);
    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:82: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]
   82 |     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: 0 / 23