Submission #1182802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182802		vux2code	Training (IOI07_training)	C++20	100 / 100	9 ms	4912 KiB

training

// Src : Vux2Code
/* Note :
    Toibingu
*/

#include <bits/stdc++.h>
#define fi first
#define se second
#define pusb push_back
#define popb pop_back
#define pusf push_front
#define popf pop_front

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;

const ll maxN = 5e3 + 5, maxLog = 20, inf64 = 1e18, inf32 = 1e9, mod = 1e9 + 7;

ll bit (ll x, ll y) {return (x >> y) & 1;}

void maxi (ll &x, ll y) {x = max (x, y);}
void mini (ll &x, ll y) {x = min (x, y);}

ll t = 1;

struct Edge {ll u, v, w, lca;};

ll n, m, dis [maxN], st [maxN], en [maxN], child [maxN], cnt, sum, f [maxN] [1 << 10], cost;
pll par [maxN], tmpU, tmpV;
vector <ll> adj [maxN];
vector <Edge> edge;

void dfs (ll x = 1, ll pr = 0) {
    dis [x] = !dis [pr];
    st [x] = ++ cnt;
    for (ll i : adj [x]) if (i != pr) {
        dfs (i, x);
        par [i] = {x, 1 << child [x] ++};  
    }
    en [x] = ++ cnt;
}

bool ckChild (ll x, ll y) {
    return st [x] <= st [y] && en [y] <= en [x];
}

ll lca (ll x, ll y) {
    while (!ckChild (x, y)) x = par [x]. fi;
    return x;
}

void solve () {
    cin >> n >> m;
    for (int i = 1, u, v, w; i <= m; i ++) {
        cin >> u >> v >> w;
        if (!w) {
            adj [u]. push_back (v);
            adj [v]. push_back (u);
        }
        cost += w;
        edge. push_back ({u, v, w});
    }
    dfs ();
    // cerr << "Check1 \n";
    for (Edge &i : edge) i. lca = lca (i. u, i. v);
    sort (edge. begin (), edge. end (), [&] (Edge x, Edge y) {return en [x. lca] < en [y. lca];});
    // cerr << "Check2 \n";
    for (Edge i : edge) {
        if (i. w && (dis [i. u] ^ dis [i. v])) continue; 
        sum = i. w; 
        for (tmpU = {i. u, 0}; tmpU. fi != i. lca; tmpU = par [tmpU. fi]) sum += f [tmpU. fi] [tmpU. se];
        for (tmpV = {i. v, 0}; tmpV. fi != i. lca; tmpV = par [tmpV. fi]) sum += f [tmpV. fi] [tmpV. se];
        // cerr << sum << '\n'; 
        for (int j = (1 << child [i. lca]) - 1; ~j; j --) {
            if (!((j & tmpU. se) || (j & tmpV. se))) {
                maxi (f [i. lca] [j], sum + f [i. lca] [j | tmpU. se | tmpV. se]);
            }
        }
    }
    // cerr << cost << ' ' << f [1] [0];
    // cerr << "Check3\n";
    cout << cost - f [1] [0];
}

int main () {
    ios::sync_with_stdio (0);
    cin.tie (0);
    cout.tie (0);
    // #define TASK "E:/Code/CP/task"
    // if (fopen (TASK".inp", "r")) {
    //     freopen (TASK".inp", "r", stdin);
    //     freopen (TASK".out", "w", stdout);
    // }
    //cin >> t;
    while (t--) solve ();
}

• 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