Submission #1039126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039126		ssense	Training (IOI07_training)	C++14	100 / 100	11 ms	4820 KiB

training

#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <cassert>

#define fr first
#define sc second

using namespace std;

#define int long long

const int N = 1005;
const int K = 10;

int n, m;

struct Edge
{
    int u, v, c, lca;
};

vector<Edge> edges;


int par[N], cat[N], child[N], order[N], depth[N];

int timer = 0;

int dp[N][1<<K];

vector<int> adj[N];

void dfs(int u, int p)
{
    par[u] = p;
    depth[u] = depth[p]+1;
    for(auto v : adj[u])
    {
        if(v != p)
        {
            dfs(v, u);
            cat[v] = child[u]++;
        }
    }
    order[u] = ++timer;
}

int find_LCA(int u, int v)
{
    if(depth[u] < depth[v])
    {
        swap(u, v);
    }
    while(depth[u] > depth[v])
    {
        u = par[u];
    }
    while(u != v)
    {
        u = par[u];
        v = par[v];
    }
    return u;
}

bool cmp(Edge a, Edge b)
{
    return order[a.lca] < order[b.lca];
}

void do_dp()
{
    for(auto e : edges)
    {
        int u = e.u, v = e.v, c = e.c, lca = e.lca;
        if(depth[u]%2 != depth[v]%2 && c != 0){continue;}
        //cout << u << " " << v << " " << c << endl;
        int tot = c;
        int mask1 = 0, mask2 = 0;
        while(u != lca)
        {
            tot+=dp[u][mask1];
            mask1 = 1<<cat[u];
            u = par[u];
        }
        while(v != lca)
        {
            tot+=dp[v][mask2];
            mask2 = 1<<cat[v];
            v = par[v];
        }
        mask1|=mask2;
        for(int mask = (1<<child[lca])-1; mask >= 0; mask--)
        {
            if((mask & mask1) != 0)
            {
                continue;
            }
            dp[lca][mask] = max(dp[lca][mask], tot+dp[lca][mask|mask1]);
        }
    }
}

void solve()
{
    cin >> n >> m;
    int sum = 0;
    for(int i = 0; i < m; i++)
    {
        int u, v, c;
        cin >> u >> v >> c;
        if(c == 0)
        {
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
            sum+=c;
            Edge e; e.u = u, e.v = v, e.c = c, e.lca = 0;
            edges.push_back(e);
    }
    //cout << endl;
    par[1] = 1;
    dfs(1, 0);
    for(auto& e : edges)
    {
        e.lca = find_LCA(e.u, e.v);
    }
    sort(edges.begin(), edges.end(), cmp);
    do_dp();
    cout << sum-dp[1][0] << endl;
}

int32_t main()
{
    int t = 1;
    //cin >> t;
    while(t--)
    {
        solve();
    }
}


/*
5 8
2 1 0
3 2 0
4 3 0
5 4 0
1 3 2
3 5 2
2 4 5
2 5 1
*/

/*
9 14
1 2 0
1 3 0
2 3 14
2 6 15
3 4 0
3 5 0
3 6 12
3 7 13
4 6 10
5 6 0
5 7 0
5 8 0
6 9 11
8 9 0
*/

/*
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <cassert>
*/

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