oj.uz

Submission #896347

# Submission time Handle Problem Language Result Execution time Memory
896347 2024-01-01T09:50:36 Z Nonoze Training (IOI07_training) C++17
30 / 100
 2 ms 604 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 460 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -