Submission #955075

#	Time	Username	Problem	Language	Result	Execution time	Memory
955075		GrindMachine	Training (IOI07_training)	C++17	100 / 100	14 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

*/

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