제출 #1318281

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318281		Ekber_Ekber	꿈 (IOI13_dreaming)	C++20	0 / 100	29 ms	10972 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;

constexpr int MAX = 2e+5 + 1, INF = 2e+9, MOD = 1e+9 + 7, K = 31;
vector <pair<int, int>> g[MAX+2];
vector <int> st(MAX+2, 0), col(MAX+2, 0);
int w;

void dfs(int u, int c=-1) {
    col[u] = 1;
    st[u] = 0;
    for (auto &i : g[u]) {
        if (i.ff == c) continue;
        dfs(i.ff, u);
        st[u] += i.ss + st[i.ff];
        w += i.ss;
    }
}

int get(int u, int c=-1) {
    for (auto &i : g[u]) {
        if (i.ff == c) continue;
        if ((st[i.ff] + i.ss) * 2 > w) return get(i.ff, u);
    }
    return u;
}

int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
    for (int i = 0; i < m; i++) {
        g[A[i] + 1].pb({B[i]+1, T[i]});
        g[B[i] + 1].pb({A[i]+1, T[i]});
    }
    vector <int> a;
    for (int i = 1; i <= n; i++) {
        if (col[i]) continue;
        w = 0;
        dfs(i);
        int c = get(i);
        dfs(c);
        int mx = 0;
        for (auto &j : g[i]) {
            mx = max(mx, st[j.ff] + j.ss);
        }
        a.pb(mx);
    }
    sort(all(a),greater<int>());
    if (a.size() == 1) return a[0];
    if (a.size() == 2) return a[0] + a[1] + L;
    return max(a[0] + a[1] + L, a[0] + a[2] + 2 * 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