oj.uz

Submission #896325

# Submission time Handle Problem Language Result Execution time Memory
896325 2024-01-01T09:19:05 Z Nonoze Training (IOI07_training) C++17
0 / 100
 300 ms 524288 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;
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-1; 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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 413 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 444 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 623 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 456 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 498 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 480 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 556 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 576 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 695 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 574 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 642 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -