oj.uz

Submission #761192

# Submission time Handle Problem Language Result Execution time Memory
761192 2023-06-19T10:51:26 Z nonono Training (IOI07_training) C++14
100 / 100
 61 ms 8628 KB 
#include "bits/stdc++.h"
#define SZ(x) (int)(x.size())
using namespace std;

const int mxN = 1005;
int n, m;
vector<vector<int>> adj(mxN);
vector<vector<array<int, 3>>> k(mxN);
vector<array<int, 3>> edge;

int h[mxN], up[mxN][11];

int id[mxN][mxN];
int dp[mxN][1 << 10], f[mxN];

void dfs(int u, int p){
    up[u][0] = p;

    for(int i = 1; i <= 10; i ++){
        up[u][i] = up[up[u][i - 1]][i - 1];
    }

    int Time = 0;
    for(int v : adj[u]){
        if(v == p) continue ;

        id[u][v] = Time ++ ;
        h[v] = h[u] + 1;
        dfs(v, u);
    }
}

int get_LCA(int u, int v){
    if(h[u] < h[v]) swap(u, v);

    int depth = h[u] - h[v];
    for(int i = 0; i <= 10; i ++){
        if(depth >> i & 1){
            u = up[u][i];
        }
    }

    if(u == v) return u;

    for(int i = 10; i >= 0; i --){
        if(up[u][i] != up[v][i]){
            u = up[u][i];
            v = up[v][i];
        }
    }

    return up[u][0];
}

int jump(int u, int x){
    if(x < 0) return u;

    for(int i = 0; i <= 10; i ++){
        if(x >> i & 1){
            u = up[u][i];
        }
    }

    return u;
}

void update(int u, int p){

    for(int i = 0; i < SZ(adj[u]); i ++){
        int v = adj[u][i];
        if(v == p) continue ;

        int x = id[u][v];
        f[v] = f[u] + dp[u][((1 << 10) - 1) ^ (1 << x)];
        update(v, u);
    }
}

void Dfs(int u, int p){

    vector<int> upd;
    for(int v : adj[u]){
        if(v == p) continue ;
        Dfs(v, u);

        int x = id[u][v];
        dp[u][(1 << x)] = max(dp[u][(1 << x)], dp[v][(1 << 10) - 1]);
    }

    update(u, p);

    for(auto [a, b, c] : k[u]){
        int x = edge[a][0];
        int y = edge[a][1];
        int w = edge[a][2];

        int mask = 0;
        if(id[u][b] != -1) mask |= (1 << id[u][b]);
        if(id[u][c] != -1) mask |= (1 << id[u][c]);

        if(!dp[u][mask]) upd.push_back(mask);

        int val = w;
        if(x != u) val += f[x] + dp[x][(1 << 10) - 1];
        if(y != u) val += f[y] + dp[y][(1 << 10) - 1];

        dp[u][mask] = max(dp[u][mask], val);
    }

    for(int i = 0; i < 10; i ++){
        int mask = 1 << i;
        upd.push_back(mask);
    }

    for(int mask = 0; mask < (1 << 10); mask ++){
        for(int x : upd){
            if((mask & x) == 0){
                dp[u][mask | x] = max(dp[u][mask | x], dp[u][mask] + dp[u][x]);
            }
        }
    }
}

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

    cin >> n >> m;

    int sum = 0;
    for(int i = 1; i <= m; i ++){
        int u, v, w;
        cin >> u >> v >> w;

        if(!w){
            adj[u].push_back(v);
            adj[v].push_back(u);
        } else {
            edge.push_back({u, v, w});
        }

        sum += w;
    }

    memset(id, -1, sizeof(id));
    dfs(1, 1);

    for(int i = 0; i < SZ(edge); i ++){
        int u = edge[i][0];
        int v = edge[i][1];

        int p = get_LCA(u, v);
        int len = h[u] + h[v] - 2 * h[p];

        u = jump(u, h[u] - h[p] - 1);
        v = jump(v, h[v] - h[p] - 1);

        if(len % 2 == 0){
            k[p].push_back({i, u, v});
        }
    }

    Dfs(1, 1);

    //for(int i = 1; i <= n; i ++) cout << dp[i][(1 << 10) - 1] << "\n";

	cout << sum - dp[1][(1 << 10) - 1] << "\n"; // 3176
    return 0;
}

Compilation message

training.cpp: In function 'void Dfs(int, int)':
training.cpp:92:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   92 |     for(auto [a, b, c] : k[u]){
      |              ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4308 KB Output is correct
2 Correct 3 ms 4340 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 8488 KB Output is correct
2 Correct 61 ms 8504 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4692 KB Output is correct
2 Correct 7 ms 4692 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5496 KB Output is correct
2 Correct 17 ms 5588 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6460 KB Output is correct
2 Correct 29 ms 6468 KB Output is correct
3 Correct 27 ms 6404 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 8480 KB Output is correct
2 Correct 50 ms 8496 KB Output is correct
3 Correct 59 ms 8480 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6372 KB Output is correct
2 Correct 29 ms 6348 KB Output is correct
3 Correct 52 ms 8544 KB Output is correct
4 Correct 30 ms 6472 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 8496 KB Output is correct
2 Correct 57 ms 8524 KB Output is correct
3 Correct 54 ms 8628 KB Output is correct
4 Correct 57 ms 8480 KB Output is correct