Submission #1262712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262712		euclid	Training (IOI07_training)	C++20	100 / 100	7 ms	4932 KiB

training

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define pb push_back
#define fi first
#define se second
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vl vector<ll>

struct edge {
    int u, v, c, l, x, y; //x, y: the indices of the two sons of l on the path from l to u, v
};

int n, m, tot = 0;
const int MN = 1007, MM = 5007, MS = (1<<10)+7;
int dep[MN], fa[MN], jump[MN][11];
vi G[MN], g[MN];
vector<edge> b, a;
vector<edge> e_lca[MN]; //e_lca[i]: all edges with l as the lca of its two endpoints
int dp[MN][MS]; //dp[i][s]: for the subtree rooted at i, excluding all children nodes in s,
//the maximum total cost we can get by adding edges into the graph
int val[MN]; //val[v]: the precomputed value of sum of dps on a path from cur node to v
vi order[11];

int bits(int x) {return __builtin_popcount(x);}
void dfs(int node, int fat) {
    fa[node] = fat;
    dep[node] = dep[fat]+1;
    for(int child : g[node]) {
        if(child == fat) continue;
        G[node].pb(child);
        dfs(child, node);
    }
}

pii lca(int u, int v) {
    int j = 10;
    if(dep[v] > dep[u]) swap(u, v);
    for(int i = 0; i <= 10; i++) {
        if((1<<i)&(dep[u]-dep[v])) u = jump[u][i];
    }
    if(u == v) return {u, u};
    while(j >= 0) {
        if(jump[u][j] != jump[v][j]) {
            u = jump[u][j];
            v = jump[v][j];
        }
        j--;
    }
    return {u, v};
}

void pushdown(int node, int fat, int v) {
    val[node] += v;
    for(int child : G[node]) {
        if(child == fat) continue;
        pushdown(child, node, v);
    }
}

void dfsdp(int node, int fat) {
    for(int child : G[node]) {
        if(child == fat) continue;
        dfsdp(child, node);
    }
    int sz = (int) G[node].size();
    //not using any edges
    for(int s = 0; s < 1<<sz; s++) {
        for(int i = 0; i < sz; i++) {
            if(((1<<i)&s)==0) {
                dp[node][s] += dp[G[node][i]][0];
            }
        }
    }
    //using some edge
    for(int s : order[sz]) {
        for(edge e : e_lca[node]) {
//            if(node == 1 && s == 0) {
//                cout << e.u << ' ' << e.v << ' ' << e.x << ' ' << e.y << '\n';
//            }
//            if(node == 5) {
//                cout << e.u << ' ' << e.v << ' ' << e.x << ' ' << e.y << '\n';
//            }
            if(e.x==-1 && e.y==-1) { //one of u, v is lca
//                cout << "here" << '\n';
                int ind = -1; //find index of son on the path from u to v
                if(dep[e.u] < dep[e.v]) swap(e.u, e.v);
                for(int i = 0; i < sz; i++) {
                    pii p = lca(e.u, G[node][i]);
                    if(p.fi==p.se) ind = i;
                }
                if((1<<ind)&s) continue;
                dp[node][s] = max(dp[node][s], dp[node][s^(1<<ind)]+e.c+dp[e.u][0]+val[e.u]);
            } else {
                if((1<<e.x)&s || (1<<e.y)&s) continue;
                dp[node][s] = max(dp[node][s], dp[node][s^(1<<e.x)^(1<<e.y)]+val[e.u]+val[e.v]+
                e.c+dp[e.u][0]+dp[e.v][0]);
                if(node == 1 && s == 0) {
//                    cout << dp[node][s^(1<<e.x)^(1<<e.y)] << ' ' << val[e.u] << ' ' << val[e.v] <<
//                    ' ' << e.c << ' ' << dp[e.u][0] << ' ' << dp[e.v][0] << '\n';
//                    cout << "cur: " << dp[node][s] << '\n';
                }
            }
//            if(s == 0 && node == 1 && dp[1][0] == 40) {
//                cout << "here: " << e.u << ' ' << e.v << '\n';
//            }
        }
    }
    //precompute val
    for(int i = 0; i < sz; i++) {
        pushdown(G[node][i], node, dp[node][1<<i]);
    }
}

int cmp(int x, int y) {
    return bits(x) > bits(y);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int x, y, z; cin >> x >> y >> z;
        if(z == 0) g[x].pb(y), g[y].pb(x);
        else b.pb({x, y, z, -1});
        tot += z;
    }
    //lca precompute
    dfs(1, 1);
    for(int i = 1; i <= n; i++) jump[i][0] = fa[i];
    for(int j = 1; j < 11; j++) {
        for(int i = 1; i <= n; i++)
            jump[i][j] = jump[jump[i][j-1]][j-1];
    }
    for(edge e : b) { // remove all edges that directly form even cycles
        pii p = lca(e.u, e.v);
        if(p.fi==p.se) e.l = p.fi;
        else e.l = fa[p.fi];
//        cout << e.u << ' ' << e.v << ' ' << e.l << '\n';
        if((-2*dep[e.l]+dep[e.u]+dep[e.v]+1)%2==1) {
            if(p.fi==p.se) e.x=e.y=-1;
            for(int i = 0; i < G[e.l].size(); i++) {
                if(G[e.l][i] == p.fi) e.x = i;
                if(G[e.l][i] == p.se) e.y = i;
//                cout << i << '\n';
            }
            a.pb(e);
            e_lca[e.l].pb(e);
//            cout << "pushed: " << e.u << ' ' << e.v << ' ' << e.x << ' ' << e.y << '\n';
        }
//        cout << e.u << ' ' << e.v << '\n';
    } //precompute order to iterate masks
    for(int sz = 1; sz <= 10; sz++) {
        for(int s = 0; s < 1<<sz; s++) order[sz].pb(s);
        sort(order[sz].begin(), order[sz].end(), cmp);
    }
    dfsdp(1, 0);
    cout << tot-dp[1][0] << '\n';
//    cout << dp[1][0] << '\n';
//    cout << lca(7, 11).fi << '\n';
//
}

• 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