Submission #1250527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250527		nrg_studio	Training (IOI07_training)	C++20	0 / 100	17 ms	4676 KiB

training

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define vec vector

const int N = 1000, K = 10, MX = (1<<K)-1;
vec<int> adj[N];
vec<array<int,3>> todo[N];
int par[N], dep[N], ind[N];
int dp[N][1<<K];

void dfs(int cur=0) {
    for (int i=0;i<adj[cur].size();i++) {
        int x = adj[cur][i];
        ind[x] = i; par[x] = cur; dep[x] = dep[cur]+1;
        adj[x].erase(find(adj[x].begin(),adj[x].end(),cur));
        dfs(x);
    }
}
int cost(const int cur, int targ, int& mask) {
    int res = dp[targ][MX];
    while (par[targ]!=cur) {
        //if (cur==1 && targ==3) {cout << dp[par[targ]][MX^(1<<ind[targ])]-dp[targ][MX];}
        res += dp[par[targ]][MX^(1<<ind[targ])]-dp[targ][MX];
        targ = par[targ];
    }
    mask |= (1<<ind[targ]);
    //if (cur==0 && targ==2) {cout<<res<<'\n';}
    return res;
}
void upd(const int cur, const int mask, const int c) {
    for (int i=MX;i>=0;i--) {
        if (i&mask) {continue;}
        chmax(dp[cur][mask|i],dp[cur][i]+c);
    }
}
void dfs2(int cur=0) {
    for (int x : adj[cur]) {
        dfs2(x);
    }
    for (int x : adj[cur]) {
        upd(cur,1<<ind[x],dp[x][MX]);
    }

    for (int i=0;i<todo[cur].size();i++) {
        int a = todo[cur][i][0], b = todo[cur][i][1], c = todo[cur][i][2];
        int mask = 0;
        c += cost(cur,a,mask);
        if (b!=-1) {c += cost(cur,b,mask);}
        upd(cur,mask,c);
    }
    for (int mask=0;mask<(1<<K);mask++) {
        for (int b=0;b<K;b++) {
            chmax(dp[cur][mask|(1<<b)],dp[cur][mask]);
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    
    par[0] = -1; dep[0] = 0;
    int n, m; cin >> n >> m;
    vec<array<int,3>> non;
    for (int i=0;i<m;i++) {
        int a, b, c; cin >> a >> b >> c;
        if (c!=0) {non.pb({--a,--b,c});}
        else {
            adj[--a].pb(--b); adj[b].pb(a);
        }
    } dfs();

    int ans = 0;
    for (int i=0;i<m-(n-1);i++) {
        int a = non[i][0], b = non[i][1], c = non[i][2];
        ans += c;
        if (dep[a]<dep[b]) {swap(a,b);}
        int dist = (dep[a]-dep[b])%2;
        int a2 = a, b2 = b;

        while (dep[a]!=dep[b]) {a = par[a];}
        
        while (par[a]!=par[b]) {
            a = par[a]; b = par[b];
        }
        if (dist==0) {
            if (a==b) {todo[b].pb({a2,-1,c});}
            else {todo[par[a]].pb({a2,b2,c});}
        }
    }

    dfs2();
    //cout << dp[2][MX^(1<<ind[4])]<<'\n';

    //cout<<ans<<'\n';
    //for (int i=0;i<n;i++) {cout<<dp[i][MX]<<' ';}

    ans -= dp[0][MX];
    cout << ans << '\n';
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 7
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9