Submission #896326

#	Time	Username	Problem	Language	Result	Execution time	Memory
896326		Nonoze	Training (IOI07_training)	C++17	0 / 100	751 ms	524288 KiB

training

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

#define int long long
#define sz(x) (int)(x.size())

int n, k, m;
vector<int> vaut;
vector<vector<pair<int, int>>> adj;
map<int, int> memo;

int dp(int s) {
    if (s>=n) return 0;
    if (memo.count(s)) return memo[s];
    int ans=dp(s+1);
    for (auto u: adj[s]) {
        ans=max(ans, dp(u.first)+u.second);
    }
    return memo[s]=ans;
}

void solve() {
    cin >> n >> m;
    vaut.clear();
    vaut.resize(n);
    adj.clear();
    adj.resize(n);
    vector<int> temp[n];
    for (int i=0; i<n-1; i++) {
        int u, v, c; cin >> u >> v >> c;
        u--, v--;
        temp[u].push_back(v);
        temp[v].push_back(u);
    }
    int act=0;
    for (int i=0; i<n; i++) {
        if (temp[i].size()==1) act=i;
    }
    int prec=0;
    for (int i=0; i<n; i++) {
        vaut[act]=i;
        int pro=act;
        for (auto u: temp[act]) {
            if (u!=prec) act=u;
        }
        prec=pro;
    }
    int ans=0;
    for (int i=n; i<m; i++) {
        int u, v, c; cin >> u >> v >> c;
        u--, v--;
        u=vaut[u], v=vaut[v];
        if (u>v) swap(v, u);
        if ((v-u)%2==0) {
            adj[u].push_back({v, c});
        }
        ans+=c;
    }
    cout << ans-dp(0) << endl;
    return;
}


signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tt=1;// cin >> tt;
    while(tt--) solve();
    return 0;
}

• 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