oj.uz

답안 #955075

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
955075 2024-03-29T10:31:59 Z GrindMachine Training (IOI07_training) C++17
100 / 100
 14 ms 12892 KB 
#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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12892 KB Output is correct
2 Correct 9 ms 12892 KB Output is correct

Subtask #4
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 2 ms 5464 KB Output is correct
3 Correct 3 ms 5724 KB Output is correct

Subtask #9
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 10588 KB Output is correct
2 Correct 8 ms 9564 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5468 KB Output is correct
2 Correct 3 ms 5976 KB Output is correct
3 Correct 14 ms 12892 KB Output is correct
4 Correct 4 ms 5980 KB Output is correct

Subtask #11
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 10584 KB Output is correct
2 Correct 14 ms 12888 KB Output is correct
3 Correct 9 ms 10236 KB Output is correct
4 Correct 8 ms 9820 KB Output is correct