Submission #319147

#	Time	Username	Problem	Language	Result	Execution time	Memory
319147		lohacho	Dreaming (IOI13_dreaming)	C++14	100 / 100	122 ms	18452 KiB

dreaming

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

using namespace std;

using LL = long long;
const int MOD = (int)1e9 + 7;
const int NS = (int)1e5 + 4;
int N, M;
vector<pair<int, int>> way[NS];
int chk[NS];
int ans, dir[NS];
vector<int> lens, sufs, hs;

pair<int, int> dfs(int x, int from){
    chk[x] = 1;
    pair<int, int> rv = {0, x};
    for(auto&nxt:way[x]){
        if(nxt.first == from){
            continue;
        }
        dir[nxt.first] = x;
        auto nval = dfs(nxt.first, x);
        nval.first += nxt.second;
        rv = max(rv, nval);
    }
    return rv;
}

void push(int now, int to){
    if(now == to){
        return;
    }
    for(auto&nxt:way[now]){
        if(nxt.first != dir[now]){
            continue;
        }
        lens.push_back(nxt.second);
        push(nxt.first, to);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i = 0; i < M; ++i){
        way[A[i]].push_back({B[i], T[i]});
        way[B[i]].push_back({A[i], T[i]});
    }
    for(int i = 0; i < N; ++i){
        if(chk[i]){
            continue;
        }
        auto rv = dfs(i, -1);
        int pa = rv.second;
        rv = dfs(pa, -1);
        int pb = rv.second;
        ans = max(ans, rv.first);
        lens.clear();
        push(pb, pa);
        sufs.clear();
        int sum = 0;
        for(int j = (int)lens.size() - 1; j >= 0; --j){
            sum += lens[j];
            sufs.push_back(sum);
        }
        reverse(sufs.begin(), sufs.end());
        int half = MOD;
        sum = 0;
        for(int j = 0; j < (int)lens.size(); ++j){
            half = min(half, max(sum, sufs[j]));
            sum += lens[j];
        }
        if((int)lens.size() == 0){
            half = 0;
        }
        hs.push_back(half);
    }
    sort(hs.begin(), hs.end()), reverse(hs.begin(), hs.end());
    if((int)hs.size() >= 2){
        ans = max(ans, hs[0] + hs[1] + L);
    }
    if((int)hs.size() >= 3){
        ans = max(ans, hs[1] + hs[2] + L * 2);
    }
    return ans;
}

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