Submission #955079

#	Time	Username	Problem	Language	Result	Execution time	Memory
955079		GrindMachine	Training (IOI07_training)	C++17	100 / 100	15 ms	12892 KiB

training

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

initially misread the problem (thought that only tree edges can be deleted)
then understood that only back edges can be deleted after reading the first few lines of the edi
didnt take any other hints from the edi

non-tree edges with odd length are forcefully deleted
instead of minimizing the sum of deleted edges, maximize the sum of staying edges

key idea:
no 2 non-tree paths can have intersecting edges
i.e each tree edge is contained in at most 1 cycle
(updated this part of the explanation after reading edi, initial explanation was not very clear)
figured out after drawing some cases

process each non-tree edge at its lca
can do bitmask dp
dp[u][mask] = max sum of staying edges if we only look at edges with lca in sub of u and we cant pick any (u,v) that come from subtree of a child that is set in mask
each node has at most 10 edges (so at most 10 subtrees), which allows us to do bitmask dp
refer code for transitions

*/

const int MOD = 1e9 + 7;
const int N = 1e3 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

vector<ll> adj[N];

struct lca_algo {
    // LCA template (for graphs with 1-based indexing)
 
    int LOG = 1;
    vector<int> depth;
    vector<vector<int>> up;
    vector<int> tin, tout;
    int timer = 1;
 
    lca_algo() {
 
    }
 
    lca_algo(int n) {
        lca_init(n);
    }
 
    void lca_init(int n) {
        while ((1 << LOG) < n) LOG++;
        up = vector<vector<int>>(n + 1, vector<int>(LOG, 1));
        depth = vector<int>(n + 1);
        tin = vector<int>(n + 1);
        tout = vector<int>(n + 1);
 
        lca_dfs(1, -1);
    }
 
    void lca_dfs(int node, int par) {
        tin[node] = timer++;
 
        trav(child, adj[node]) {
            if (child == par) conts;

            up[child][0] = node;
            rep1(j, LOG - 1) {
                up[child][j] = up[up[child][j - 1]][j - 1];
            }
 
            depth[child] = depth[node] + 1;
 
            lca_dfs(child, node);
        }
 
        tout[node] = timer-1;
    }
 
    int lift(int u, int k) {
        rep(j, LOG) {
            if (k & (1 << j)) {
                u = up[u][j];
            }
        }
 
        return u;
    }

    int query(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        int k = depth[u] - depth[v];
        u = lift(u, k);
 
        if (u == v) return u;
 
        rev(j, LOG - 1, 0) {
            if (up[u][j] != up[v][j]) {
                u = up[u][j];
                v = up[v][j];
            }
        }
 
        u = up[u][0];
        return u;
    }
 
    int get_dis(int u, int v) {
        int lca = query(u, v);
        return depth[u] + depth[v] - 2 * depth[lca];
    }
 
    bool is_ances(int u, int v){
        return tin[u] <= tin[v] and tout[u] >= tout[v];
    }
};

lca_algo LCA;
vector<array<ll,3>> here[N];
vector<ll> par(N);
ll dp[N][1<<10];
ll adj_pos[N][N];

void dfs1(ll u){
    auto &children = adj[u];
    ll siz = sz(children);

    trav(v,children){
        dfs1(v);
    }

    ll best[siz][siz];
    memset(best,-0x3f,sizeof best);

    for(auto [x,y,w] : here[u]){
        vector<ll> path1,path2;

        {
            ll i = x;
            while(i != u){
                path1.pb(i);
                i = par[i];
            }
        }

        {
            ll i = y;
            while(i != u){
                path2.pb(i);
                i = par[i];
            }
        }

        ll cost = w;
        ll jbx = -1, jby = -1;

        if(!path1.empty()){
            cost += dp[path1[0]][0];
            rep1(i,sz(path1)-1){
                ll id = adj_pos[path1[i]][path1[i-1]];
                cost += dp[path1[i]][1<<id];
            }
            jbx = path1.back();
        }

        if(!path2.empty()){
            cost += dp[path2[0]][0];
            rep1(i,sz(path2)-1){
                ll id = adj_pos[path2[i]][path2[i-1]];
                cost += dp[path2[i]][1<<id];
            }
            jby = path2.back();
        }

        assert(!(jbx == -1 and jby == -1));

        if(jbx == -1) jbx = jby;
        if(jby == -1) jby = jbx;

        jbx = adj_pos[u][jbx];
        jby = adj_pos[u][jby];
        amax(best[jbx][jby],cost);
    }

    rep(i,siz){
        ll v = children[i];
        amax(best[i][i],dp[v][0]);
    }

    rev(mask,(1<<siz)-1,0){
        rep(x,siz){
            if(mask&(1<<x)) conts;
            rep(y,siz){
                if(mask&(1<<y)) conts;
                amax(dp[u][mask],best[x][y]+dp[u][mask|(1<<x)|(1<<y)]);
            }
        }
    }
}

void solve(int test_case)
{
    ll n,m; cin >> n >> m;
    vector<array<ll,3>> edges;

    rep1(i,m){
        ll u,v,w; cin >> u >> v >> w;
        if(!w){
            adj[u].pb(v), adj[v].pb(u);
        }
        else{
            edges.pb({u,v,w});
        }
    }

    LCA = lca_algo(n);
    ll sum = 0;

    for(auto [u,v,w] : edges){
        sum += w;
        if((LCA.depth[u]&1) != (LCA.depth[v]&1)) conts;
        ll lca = LCA.query(u,v);
        here[lca].pb({u,v,w});   
    }

    rep1(i,n){
        par[i] = LCA.up[i][0];
    }

    for(int i = 2; i <= n; ++i){
        adj[i].erase(find(all(adj[i]),par[i]));
    }
    rep1(i,n){
        sort(all(adj[i]));
    }

    rep1(u,n){
        ll ptr = 0;
        trav(v,adj[u]){
            adj_pos[u][v] = ptr++;
        }
    }

    dfs1(1);

    ll ans = sum-dp[1][0];
    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

• 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