oj.uz

Submission #909256

# Submission time Handle Problem Language Result Execution time Memory
909256 2024-01-17T06:35:57 Z lighton Magic Tree (CEOI19_magictree) C++17
6 / 100
 2000 ms 860964 KB 
#include<bits/stdc++.h>
#define forf(i,a,b) for(int i = a; i<=b; i++)
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
int N,M,K;
int inf = 1e9;
struct ST{
    int t; ll v; int id;
    bool operator<(const ST &r) const{
        if(t==r.t) return id<r.id;
        return t<r.t;
    }
};
set<ST> s[200001];
vector<int> adj[200001];
ST upd[200001];

set<ST> merg (set<ST> a, set<ST> b){
    set<ST> ret;
    for(ST i : a) ret.insert(i);
    for(ST i : b) ret.insert(i);
    return ret;
}
void add (set<ST> &now, ST a){
    ST tmp = a; tmp.id = inf;
    now.insert(a);
    auto it = now.upper_bound(tmp);
    ll sum = 0; int flag = 0;
    ST nxt;
    while(it != now.end() && sum <= a.v){
        sum += it->v;
        if(sum > a.v){
            nxt = *it;
            flag = 1;
        }
        it = now.erase(it);
    }
    if(flag){
        nxt.v = sum-a.v;
        now.insert(nxt);
    }
}

void dfs(int now ,int p = -1){
    for(int &i : adj[now]){
        if(i==p) continue;
        dfs(i,now);
        s[now] = merg(s[now],s[i]);
    }
    if(upd[now].id) add(s[now],upd[now]);
}

int main(){
    scanf("%d %d %d" , &N,&M,&K);
    forf(i,2,N){
        int t; scanf("%d" , &t);
        adj[i].push_back(t);
        adj[t].push_back(i);
    }
    forf(i,1,M){
        int u,t; ll v; scanf("%d %d %lld" , &u,&t, &v);
        upd[u] = {t,v,i};
    }
    dfs(1);
    ll ans = 0;
    for(ST i : s[1]) ans += i.v;
    printf("%lld" , ans);
}

Compilation message

magictree.cpp: In function 'int main()':
magictree.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%d %d %d" , &N,&M,&K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:57:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         int t; scanf("%d" , &t);
      |                ~~~~~^~~~~~~~~~~
magictree.cpp:62:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         int u,t; ll v; scanf("%d %d %lld" , &u,&t, &v);
      |                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 4 ms 15092 KB Output is correct
3 Correct 4 ms 14940 KB Output is correct
4 Correct 4 ms 14940 KB Output is correct
5 Correct 5 ms 14940 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 6 ms 14936 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 44172 KB Output is correct
2 Execution timed out 2069 ms 727132 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15196 KB Output is correct
2 Correct 9 ms 16728 KB Output is correct
3 Correct 47 ms 30880 KB Output is correct
4 Correct 146 ms 92860 KB Output is correct
5 Execution timed out 2097 ms 682424 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1124 ms 94372 KB Output is correct
2 Correct 1159 ms 102276 KB Output is correct
3 Execution timed out 2075 ms 699312 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 4 ms 15092 KB Output is correct
3 Correct 4 ms 14940 KB Output is correct
4 Correct 4 ms 14940 KB Output is correct
5 Correct 5 ms 14940 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 6 ms 14936 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct
10 Correct 859 ms 83172 KB Output is correct
11 Correct 844 ms 82168 KB Output is correct
12 Execution timed out 2088 ms 860964 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 18264 KB Output is correct
2 Correct 47 ms 23124 KB Output is correct
3 Correct 59 ms 23024 KB Output is correct
4 Correct 42 ms 23124 KB Output is correct
5 Execution timed out 2017 ms 23308 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 4 ms 15092 KB Output is correct
3 Correct 4 ms 14940 KB Output is correct
4 Correct 4 ms 14940 KB Output is correct
5 Correct 5 ms 14940 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 6 ms 14936 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct
10 Correct 5 ms 15196 KB Output is correct
11 Correct 9 ms 16728 KB Output is correct
12 Correct 47 ms 30880 KB Output is correct
13 Correct 146 ms 92860 KB Output is correct
14 Execution timed out 2097 ms 682424 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 4 ms 15092 KB Output is correct
3 Correct 4 ms 14940 KB Output is correct
4 Correct 4 ms 14940 KB Output is correct
5 Correct 5 ms 14940 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 6 ms 14936 KB Output is correct
9 Correct 4 ms 14940 KB Output is correct
10 Correct 387 ms 44172 KB Output is correct
11 Execution timed out 2069 ms 727132 KB Time limit exceeded
12 Halted 0 ms 0 KB -