제출 #1148702

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148702		Tsagana	Dreaming (IOI13_dreaming)	C++20	0 / 100	30 ms	14912 KiB

dreaming

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

#define all(x) x.begin(), x.end()
#define lnl long long
#define pii pair<int, int>
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

int d[3][100010];
int f[100010];
int W[100010];
int w, e, D, R;
int X = -1, Y = -1, Z = -1;
vector<pii> adj[100010];

void dfs(int x, int o)
{
    f[x]++;
    if (o < 2 && d[o][x] >= D) {e = x; D = d[o][x];}
    if (o > 1) D = min(D, max(d[1][x], d[2][x]));
    for (auto y: adj[x])
    {
        if (f[y.F] == o) continue ;
        d[o][y.F] = d[o][x] + y.S;
        dfs(y.F, o);
    }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    while(M--)
    {
        adj[A[M]].pb({B[M], T[M]});
        adj[B[M]].pb({A[M], T[M]});
    }
    while(N--)
    {
        if (f[N]) continue ;
        dfs(N, 0);
        dfs(e, 1);
        R = max(R, D);
        dfs(e, 2);
        W[w++] = D;
        D = 0;
    }
    while(w--)
    {
        if (Z < W[w]) Z = W[w];
        if (Y < W[w]) {Z = Y; Y = W[w];}
        if (X < W[w]) {Y = X; X = W[w];}
    }
    return max(R, max(X, Z + (Z >= 0) * L) + Y + (Y >= 0) * L);
}

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