oj.uz

Submission #1099384

# Submission time Handle Problem Language Result Execution time Memory
1099384 2024-10-11T08:56:28 Z RiverFlow Magic Tree (CEOI19_magictree) C++14
47 / 100
 2000 ms 33108 KB 
#include <bits/stdc++.h>

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b) { a = b; return 1; } return 0;
}

const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;

void prepare(); void main_code();

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    const bool MULTITEST = 0; prepare();
    int num_test = 1; if (MULTITEST) cin >> num_test;
    while (num_test--) { main_code(); }
}

void prepare() {};

int n, m, k;

int s[N], y[N], re[N];
pair<int, int> a[N];
vector<int> g[N], adj[N];

int cnt = 0;

void dfs(int u) {
    s[u] = y[u];
    vec<int> c;
    for(int v : g[u]) {
        dfs(v);
        s[u] += s[v];
        if (s[v] > 0) {
            c.push_back(v);
        }
    }
    if (!y[u] and sz(c) == 0) {
        re[u] = -1;
        return ;
    }
    if (!y[u]) {
        if (sz(c) == 1) {
            re[u] = re[c.back()];
            return ;
        }
        re[u] = u;
        for(int v : c)
            adj[u].push_back(re[v]);
        return ;
    }
    re[u] = u;
    for(int v : c)
        adj[u].push_back(re[v]);
}

bool on[N];

long long dp[N];

void dfx(int u, int d, long long &c) {
    if (on[u]) {
        c += dp[u];
        return ;
    }
    for(int v : adj[u]) {
        dfx(v, d, c);
    }
}
void dfs2(int u, int D) {
    long long s = 0;
    for(int v : adj[u]) {
        dfs2(v, D);
        s += dp[v];
    }
    maxi(dp[u], s);
    long long nw = 0;
    if (y[u] and a[u].fi == D) {
        dfx(u, a[u].first, nw);
        maxi(dp[u], nw + a[u].se);
    }

    if (a[u].fi == D)
        on[u] = 1;
}
void main_code() {
    cin >> n >> m >> k;
    for(int i = 2; i <= n; ++i) {
        int x; cin >> x;
        g[x].push_back(i);
    }
    y[1] = 1; a[1] = _mp(k + 1, 0);
    vec<bool> ex(k + 1, 0);
    for(int i = 1; i <= m; ++i) {
        int v, d, w; cin >> v >> d >> w;
        y[v] = 1;
        a[v] = _mp(d, w);
        ex[d] = 1;
    }
    dfs(1);
    for(int i = 1; i <= k; ++i) if (ex[i]) {
        dfs2(1, i);
    }
    cout << dp[1];

}


/*     Let the river flows naturally     */

Compilation message

magictree.cpp: In function 'int main()':
magictree.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 9816 KB Output is correct
5 Correct 4 ms 9884 KB Output is correct
6 Correct 4 ms 9832 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 4 ms 9820 KB Output is correct
9 Correct 4 ms 10072 KB Output is correct

Subtask #2
0 / 3.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10076 KB Output is correct
2 Correct 6 ms 10076 KB Output is correct
3 Correct 5 ms 10076 KB Output is correct
4 Execution timed out 2095 ms 32552 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 17768 KB Output is correct
2 Correct 62 ms 17928 KB Output is correct
3 Correct 46 ms 24656 KB Output is correct
4 Correct 27 ms 15192 KB Output is correct
5 Correct 44 ms 33108 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 9816 KB Output is correct
5 Correct 4 ms 9884 KB Output is correct
6 Correct 4 ms 9832 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 4 ms 9820 KB Output is correct
9 Correct 4 ms 10072 KB Output is correct
10 Correct 80 ms 17236 KB Output is correct
11 Correct 61 ms 17132 KB Output is correct
12 Correct 67 ms 24004 KB Output is correct
13 Correct 31 ms 14456 KB Output is correct
14 Correct 66 ms 32552 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 10844 KB Output is correct
2 Correct 27 ms 14676 KB Output is correct
3 Correct 28 ms 14684 KB Output is correct
4 Correct 37 ms 14776 KB Output is correct
5 Correct 15 ms 13276 KB Output is correct
6 Correct 52 ms 17160 KB Output is correct
7 Correct 43 ms 20828 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 9816 KB Output is correct
5 Correct 4 ms 9884 KB Output is correct
6 Correct 4 ms 9832 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 4 ms 9820 KB Output is correct
9 Correct 4 ms 10072 KB Output is correct
10 Correct 7 ms 10076 KB Output is correct
11 Correct 6 ms 10076 KB Output is correct
12 Correct 5 ms 10076 KB Output is correct
13 Execution timed out 2095 ms 32552 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 9816 KB Output is correct
5 Correct 4 ms 9884 KB Output is correct
6 Correct 4 ms 9832 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 4 ms 9820 KB Output is correct
9 Correct 4 ms 10072 KB Output is correct
10 Execution timed out 2063 ms 15448 KB Time limit exceeded
11 Halted 0 ms 0 KB -