제출 #1270501

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270501		dorkikann	Training (IOI07_training)	C++20	30 / 100	2 ms	584 KiB

training

#include <bits/stdc++.h>
using namespace std;

const int N = 2e3 + 5;

vector<int> Graph[N];
vector<tuple<int, int, int>> Edges;

int Depth[N];
vector<pair<int, int>> Check[N];

int Solution[N];

void DFS1(int u, int parent)
{
    Depth[u] = Depth[parent] + 1;

    for(auto v : Graph[u]) {
        if(v != parent)
            DFS1(v, u);
    }
}

void Fix()
{
    for(auto [a, b, c] : Edges) {
        if(c == 0 || ((Depth[a] % 2) != (Depth[b] % 2)))
            continue;

        if(Depth[a] > Depth[b])
            Check[b].push_back({a, c});
        else
            Check[a].push_back({b, c});
    }
}

void DFS2(int u, int parent)
{
    Solution[u] = 0;
    for(auto v : Graph[u]) {
        if(v != parent) {
            DFS2(v, u);
            Solution[u] = max(Solution[u], Solution[v]);
        }
    }

    for(auto [v, c] : Check[u])
        Solution[u] = max(Solution[u], Solution[v] + c);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m, a, b, c;

    cin >> n >> m;

    int sum = 0;
    for(int i = 0; i < m; i++) {
        cin >> a >> b >> c;

        if(c == 0) {
            Graph[a].push_back(b);
            Graph[b].push_back(a);
        }
        sum += c;
        Edges.push_back({a, b, c});
    }
    int start = 1;
    for(int i = 1; i <= n; i++) {
        if(Graph[i].size() == 1)
            start = i;
    }

    DFS1(start, 0);
    Fix();

    DFS2(start, 0);
    cout << (sum - Solution[start]) << "\n";

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 7
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9