Submission #1270528

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270528		dorkikann	Training (IOI07_training)	C++20	30 / 100	19 ms	8520 KiB

training

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

const int N = 2e3 + 5;
const int P = 11;
const int M = (1<<P);

int Solution[N][M];

vector<int> Graph[N];
pair<int, int> Parents[N];
int Depth[N];

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

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

    for(int i = 0; i < Graph[u].size(); i++) {
        int v = Graph[u][i];

        if(v != parent)
            DFS1(v, u, i);
    }
}

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

        if(Depth[u] > Depth[v])
            swap(u, v);
        while(Depth[u] != Depth[v]) 
            v = Parents[v].first;
        while(u != v) {
            u = Parents[u].first;
            v = Parents[v].first;
        }

        Check[u].push_back({a, b, c});
    }
}

pair<int, int> Find(int u, int idx, int limit)
{
    if(u == limit)
        return {0, idx};

    int val = 0;
    if(idx != -1)
        Solution[u][(M-1) ^ (1<<idx)];
    else
        val = Solution[u][M-1];

    pair<int, int> sol = Find(Parents[u].first, Parents[u].second, limit);

    return {sol.first + val, sol.second};
}

void DFS2(int u)
{
    for(auto v : Graph[u]) {
        if(v != Parents[u].first)
            DFS2(v);
    }

    for(int i = 0; i < Graph[u].size(); i++) {
        int add = Solution[Graph[u][i]][M-1];

        for(int j = 0; j < M; j++) {
            if(j & (1<<i))
                Solution[u][j] = max(Solution[u][j], Solution[u][j ^ (1<<i)] + add);
        }
    }

    for(auto [a, b, c] : Check[u]) {
        pair<int, int> x = Find(a, -1, u);
        pair<int, int> y = Find(b, -1, u);

        int cost = x.first + y.first + c;
        int mask = 0;
        if(x.second != -1)
            mask |= (1<<(x.second));
        if(y.second != -1)
            mask |= (1<<(y.second));

        for(int j = 0; j < M; j++) {
            if((j & mask) == mask)
                Solution[u][j] = max(Solution[u][j], Solution[u][j ^ mask] + cost);
        }
    }
}

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);
        }
        Edges.push_back({a, b, c});
        sum += c;
    }
    DFS1(1, 0, 0);
    Fix();

    DFS2(1);
    cout << (sum - Solution[1][M-1]) << "\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