Submission #2695812


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define fin cin
#define fout cout
//ifstream fin("x.in"); ofstream fout("x.out");

typedef long long i64;
const int nmax = 1e5;
const int mod = 1e9 + 7;

i64 ans;

vector<pair<int, int>> g[nmax + 1];
int d[nmax + 1], mxfiu[nmax + 1];
bool viz[nmax + 1];

void dfs (int nod, int val) {
    viz[nod] = 1;

    d[nod] = 1;
    for (auto i : g[nod]) {
        if (viz[i.first] == 0) {
            dfs(i.first, i.second);

            d[nod] += d[i.first];
            mxfiu[nod] = max(mxfiu[nod], d[i.first]);
        }
    }

    ans += 2LL * val * d[nod];
}

int main() {
    fin.sync_with_stdio(false); fin.tie(); fout.tie();

    int n;
    fin >> n;

    for (int i = 1; i < n; ++ i) {
        int x, y, z;
        fin >> x >> y >> z;
        g[x].push_back({y, z});
        g[y].push_back({x, z});
    }

    dfs(1, 0);

    int cen = -1;
    for (int i = 1; i <= n; ++ i) {
        if (mxfiu[i] <= n / 2 && n - d[i] <= n / 2) {
            cen = i;
        }
    }

    memset(viz, 0, sizeof(viz));

    ans = 0;
    dfs(cen, 0);

    int mn = 1 << 30;
    int cnt = 0, lst = 0;

    for (auto i : g[cen])
        mn = min(mn, i.second);

    for (auto i : g[cen]) {
        if (2 * d[i.first] == n) {
            ++ cnt;
            lst = i.second;
        }
    }

    if (cnt == 1)
        mn = lst;

    ans -= mn;
    fout << ans << "\n";

    return 0;
}

Submission Info

Submission Time
Task D - Tree and Hamilton Path
User laurageorgescu
Language C++14 (GCC 5.4.1)
Score 1100
Code Size 1494 Byte
Status AC
Exec Time 60 ms
Memory 10624 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1100 / 1100
Status
AC × 2
AC × 38
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All sample_01.txt, sample_02.txt, sample_01.txt, sample_02.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt
Case Name Status Exec Time Memory
sample_01.txt AC 2 ms 2688 KB
sample_02.txt AC 2 ms 2688 KB
subtask_1_01.txt AC 2 ms 2688 KB
subtask_1_02.txt AC 51 ms 6656 KB
subtask_1_03.txt AC 26 ms 4864 KB
subtask_1_04.txt AC 54 ms 7040 KB
subtask_1_05.txt AC 30 ms 5888 KB
subtask_1_06.txt AC 22 ms 4604 KB
subtask_1_07.txt AC 23 ms 4608 KB
subtask_1_08.txt AC 28 ms 4992 KB
subtask_1_09.txt AC 18 ms 4224 KB
subtask_1_10.txt AC 8 ms 3584 KB
subtask_1_11.txt AC 15 ms 4096 KB
subtask_1_12.txt AC 56 ms 7168 KB
subtask_1_13.txt AC 56 ms 7168 KB
subtask_1_14.txt AC 56 ms 7168 KB
subtask_1_15.txt AC 56 ms 7168 KB
subtask_1_16.txt AC 56 ms 7168 KB
subtask_1_17.txt AC 56 ms 7168 KB
subtask_1_18.txt AC 56 ms 7168 KB
subtask_1_19.txt AC 56 ms 7168 KB
subtask_1_20.txt AC 56 ms 7168 KB
subtask_1_21.txt AC 56 ms 7168 KB
subtask_1_22.txt AC 57 ms 7168 KB
subtask_1_23.txt AC 60 ms 9728 KB
subtask_1_24.txt AC 59 ms 10368 KB
subtask_1_25.txt AC 56 ms 7168 KB
subtask_1_26.txt AC 58 ms 8192 KB
subtask_1_27.txt AC 59 ms 10112 KB
subtask_1_28.txt AC 56 ms 7168 KB
subtask_1_29.txt AC 59 ms 10624 KB
subtask_1_30.txt AC 58 ms 9600 KB
subtask_1_31.txt AC 49 ms 7160 KB
subtask_1_32.txt AC 49 ms 7160 KB
subtask_1_33.txt AC 29 ms 5752 KB
subtask_1_34.txt AC 39 ms 7028 KB