제출 #456976

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
456976		PPAP_1264589	Dreaming (IOI13_dreaming)	C++17	100 / 100	123 ms	16624 KiB

dreaming

#include <bits/stdc++.h>
#include"dreaming.h"
#define pii pair<int, int>
#define f first
#define s second
#define up(i, a, b) for (int i = (a); i <= (b); i++)
#define pb push_back
using namespace std;

const int oo = 2*1000000001;
const int maxn = 100001;
vector<pii> a[maxn];
int n,m,L;

bool dd[maxn];
int maxx = -1;
vector<int> luu;
int P = 0;
void DFS(int u, int parent, int d[]){
    if (!dd[u]) luu.emplace_back(u);
    dd[u] = 1;
    for (pii x : a[u]){
        int v = x.f;
        int w = x.s;
        if (v == parent) continue;

        d[v] = d[u] + w;
        DFS(v, u, d);
    }
    if (d[P] < d[u]) P = u;
    maxx = max(maxx, d[u]);
}

int cost[maxn];
int dx[maxn];
int dy[maxn];
vector<int> R;
void find_center(int root){
    P = 0;
    DFS(root, -1, cost);
    int X = P;

    P = 0;
    DFS(X, -1, dx);
    int Y = P;

    DFS(Y, -1, dy);

    int minn = oo;
    for (int i : luu){
        minn = min(minn, max(dx[i], dy[i]));
        cost[i] = dx[i] = dy[i] = 0;
    }

    luu.clear();
    R.push_back(minn);
}

int travelTime(int n, int m, int L, int AA[], int BB[], int TT[]){
    up(i, 0, m-1){
        int u = AA[i];
        u++;
        int v = BB[i];
        v++;
        int w = TT[i];
        a[u].pb(make_pair(v, w));
        a[v].pb(make_pair(u, w));
    }
    if (m == n-1){
        P = 0;
        DFS(1, -1, cost);
        int X = P;
        P = 0;
        fill(cost, cost+n+1, 0);
        DFS(X, -1, cost);
        return cost[P];
    }
    up(root, 1, n){
        if (!dd[root]){
            find_center(root);
        }
    }

    int tplt = R.size();
    sort(R.begin(), R.end(), greater<int>());

    if (tplt > 1){
        maxx = max(maxx, R[0] + R[1] + L);
    }
    if (tplt > 2){
        maxx = max(maxx, R[1] + R[2] + L*2);
    }
    return maxx;
}

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