oj.uz

Submission #1039126

# Submission time Handle Problem Language Result Execution time Memory
1039126 2024-07-30T13:20:00 Z ssense Training (IOI07_training) C++14
100 / 100
 11 ms 4820 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4700 KB Output is correct
2 Correct 6 ms 4800 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 2 ms 1116 KB Output is correct
3 Correct 2 ms 1760 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2264 KB Output is correct
2 Correct 4 ms 1268 KB Output is correct
3 Correct 4 ms 1496 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 1880 KB Output is correct
3 Correct 11 ms 4820 KB Output is correct
4 Correct 3 ms 1884 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2264 KB Output is correct
2 Correct 11 ms 4568 KB Output is correct
3 Correct 6 ms 1752 KB Output is correct
4 Correct 4 ms 1752 KB Output is correct