Submission #1113870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113870		kiethm07	Dreaming (IOI13_dreaming)	C++11	100 / 100	54 ms	18752 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"

#define pii pair<int,int>
#define pli pair<long long,pii>
#define fi first
#define se second

#define vi vector<int>
#define vii vector<pii>
#define all(x) x.begin(),x.end()

using namespace std;

typedef long long ll;
typedef long double ld;

const int inf = 1e9;
const ll linf = 1e16;
const double pi = acos(-1);
const int maxN = 1e5 + 5;

vector<pii> a[maxN];
int down[maxN];
int up[maxN];
int ans = 0;

void dfsDown(int u,int p){
    down[u] = 0;
    for (int i = 0; i < a[u].size(); i++){
        int v,w;
        tie(v,w) = a[u][i];
        if (v == p) continue;
        dfsDown(v,u);
        down[u] = max(down[u], down[v] + w);
    }
}

void dfsUp(int u,int p,int& res){
    res = min(res, max(down[u], up[u]));
    ans = max(ans, down[u] + up[u]);
    int m1 = -1,m2 = -1;
    int i1 = -1,i2 = -1;
    for (int i = 0; i < a[u].size(); i++){
        int v = a[u][i].fi;
        int w = a[u][i].se;
        if (v == p) continue;
        if (down[v] + w > m2){
            m2 = down[v] + w;
            i2 = v;
        }
        if (m2 > m1){
            swap(m2,m1);
            swap(i2,i1);
        }
    }
    for (int i = 0; i < a[u].size(); i++){
        int v = a[u][i].fi;
        int w = a[u][i].se;
        if (v == p) continue;
        if (i1 == v && i2 == -1){
            up[v] = up[u] + w;
        }
        else{
            up[v] = max(up[u] + w,(v == i1 ? m2 : m1) + w);
        }
        dfsUp(v,u,res);
    }
}

int getVal(int u){
    dfsDown(u,-1);
    int res = inf;
    dfsUp(u,-1,res);
    return res;
}

int travelTime(int N,int M,int L,int A[],int B[],int T[]){
    for (int i = 0; i < M; i++){
        int u = A[i] + 1;
        int v = B[i] + 1;
        int w = T[i];
        a[u].push_back(pii(v,w));
        a[v].push_back(pii(u,w));
    }
    vector<int> v;
    memset(down,-1,sizeof(down));
    for (int i = 1; i <= N; i++){
        if (down[i] != -1) continue;
        v.push_back(getVal(i));
    }
    sort(all(v),greater<int>());
    if (v.size() == 2) ans = max(ans, v[0] + v[1] + L);
    if (v.size() >= 3) ans = max(ans, max(v[0] + v[1] + L, v[1] + v[2] + L + L));
    return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfsDown(int, int)':
dreaming.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 0; i < a[u].size(); i++){
      |                     ~~^~~~~~~~~~~~~
dreaming.cpp: In function 'void dfsUp(int, int, int&)':
dreaming.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int i = 0; i < a[u].size(); i++){
      |                     ~~^~~~~~~~~~~~~
dreaming.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int i = 0; i < a[u].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