oj.uz

Submission #1099402

# Submission time Handle Problem Language Result Execution time Memory
1099402 2024-10-11T09:15:47 Z RiverFlow Magic Tree (CEOI19_magictree) C++14
47 / 100
 2000 ms 33616 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);
    }
}
int t[N];
void dfs2(int u, int D) {
    long long s = 0;
    for(int v : adj[u]) {
        dfs2(v, D);
        t[u]+=t[v];
        s += dp[v];
    }

    maxi(dp[u], s);
    long long nw = 0;
    if (y[u] and a[u].fi == D) {
        dp[u] = s + 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 'void dfs2(int, int)':
magictree.cpp:106:15: warning: unused variable 'nw' [-Wunused-variable]
  106 |     long long nw = 0;
      |               ^~
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 5 ms 9816 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 5 ms 9860 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 4 ms 9872 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 4 ms 9660 KB Output is correct
9 Correct 5 ms 9816 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 15956 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 7 ms 10076 KB Output is correct
3 Correct 7 ms 10076 KB Output is correct
4 Execution timed out 2090 ms 32816 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 18260 KB Output is correct
2 Correct 42 ms 18260 KB Output is correct
3 Correct 40 ms 24892 KB Output is correct
4 Correct 24 ms 15184 KB Output is correct
5 Correct 51 ms 33616 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 5 ms 9860 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 4 ms 9872 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 4 ms 9660 KB Output is correct
9 Correct 5 ms 9816 KB Output is correct
10 Correct 80 ms 17484 KB Output is correct
11 Correct 68 ms 17496 KB Output is correct
12 Correct 62 ms 24160 KB Output is correct
13 Correct 32 ms 14456 KB Output is correct
14 Correct 59 ms 32848 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 10840 KB Output is correct
2 Correct 29 ms 14928 KB Output is correct
3 Correct 30 ms 14932 KB Output is correct
4 Correct 43 ms 14932 KB Output is correct
5 Correct 16 ms 13360 KB Output is correct
6 Correct 49 ms 17496 KB Output is correct
7 Correct 45 ms 21076 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 5 ms 9860 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 4 ms 9872 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 4 ms 9660 KB Output is correct
9 Correct 5 ms 9816 KB Output is correct
10 Correct 7 ms 10076 KB Output is correct
11 Correct 7 ms 10076 KB Output is correct
12 Correct 7 ms 10076 KB Output is correct
13 Execution timed out 2090 ms 32816 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 5 ms 9860 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 4 ms 9872 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 4 ms 9660 KB Output is correct
9 Correct 5 ms 9816 KB Output is correct
10 Execution timed out 2062 ms 15956 KB Time limit exceeded
11 Halted 0 ms 0 KB -