Submission #896347

#	Time	Username	Problem	Language	Result	Execution time	Memory
896347		Nonoze	Training (IOI07_training)	C++17	30 / 100	2 ms	604 KiB

training

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

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

using namespace std;
//using namespace __gnu_pbds;

/*typedef
tree<
  int,
  null_type,
  less<int>,
  rb_tree_tag,
  tree_order_statistics_node_update>
ordered_set;*/

int n, k, m;
vector<int> vaut;
vector<vector<pair<int, int>>> adj;
vector<int> memo(1005, -1);

int dp(int s) {
    if (s>=n) return 0;
    if (memo[s]!=-1) return memo[s];
    int ans=dp(s+1);
    for (auto u: adj[s]) {
        if (u.first>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];
    vector<pair<pair<int, int>, int>> temptemp;
    for (int i=0; i<m; i++) {
        int u, v, c; cin >> u >> v >> c;
        u--, v--;
        if (c==0) {
            temp[u].push_back(v);
            temp[v].push_back(u);
        } else {
            temptemp.push_back({{u, v}, c});
        }
    }
    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-1; i<m; i++) {
        int u=temptemp[i-n+1].first.first, v=temptemp[i-n+1].first.second;
        int c=temptemp[i-n+1].second;
        u=vaut[u], v=vaut[v];
        if (u>v) swap(u, v);
        if (u!=v && (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: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 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