oj.uz

Submission #583356

# Submission time Handle Problem Language Result Execution time Memory
583356 2022-06-25T09:20:47 Z 79brue Magic Tree (CEOI19_magictree) C++17
0 / 100
 2000 ms 18784 KB 
#include <bits/stdc++.h>
#ifndef TEST
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#endif

using namespace std;

typedef long long ll;

map<int, ll> mp[200002];

void update(int i, int x, ll v){ /// v만큼 더한다
    mp[i][x] += v;
}

bool nextRemove(int i, int x, ll v){
    auto it = mp[i].upper_bound(x);
    while(v && it != mp[i].end()){
        pair<int, ll> tp = *it;
        ll tmp = min(tp.second, v);
        mp[i][tp.first] -= tmp;
        v -= tmp;
        if(!mp[i][tp.first]) mp[i].erase(tp.first);
        it = mp[i].upper_bound(x);
    }
}

void mergeSet(int l, int r){
    if(mp[l].size() < mp[r].size()) mp[l].swap(mp[r]);
    for(auto x: mp[r]){
        mp[l][x.first] += x.second;
    }
    mp[r].clear();
}

struct Fruit{
    int v, d; ll w;
    Fruit(){}
    Fruit(int v, int d, ll w): v(v), d(d), w(w){}
};

int n, m, k;
int par[100002];
vector<int> child[100002];
int state[100002];
Fruit fruit[100002];

int day[100002];
ll weight[100002];
int root[100002];

void renumber(){
    vector<int> dVec;
    for(int i=1; i<=m; i++) dVec.push_back(fruit[i].d);
    sort(dVec.begin(), dVec.end());
    dVec.erase(unique(dVec.begin(), dVec.end()), dVec.end());
    for(int i=1; i<=m; i++) fruit[i].d = lower_bound(dVec.begin(), dVec.end(), fruit[i].d) - dVec.begin() + 1;
    k = (int)dVec.size();
}

int vcnt;
void dfs(int x){
    for(auto y: child[x]){
        dfs(y);
        mergeSet(x, y);
    }
    if(day[x]){
        update(x, day[x], weight[x]);
        nextRemove(x, day[x], weight[x]);
    }
//    printf("mp[%d]: ", x);
//    for(auto p: mp[x]) printf("(%d, %lld) ", p.first, p.second);
//    puts("");
}

int main(){
//    freopen("output.txt", "r", stdin);
    scanf("%d %d %d", &n, &m, &k);
    for(int i=2; i<=n; i++){
        scanf("%d", &par[i]);
        child[par[i]].push_back(i);
    }

    for(int i=1; i<=m; i++){
        int v, d, w;
        scanf("%d %d %d", &v, &d, &w);
        fruit[i] = Fruit(v, d, w);
    }
    renumber();
    for(int i=1; i<=m; i++){
        day[fruit[i].v] = fruit[i].d;
        weight[fruit[i].v] = fruit[i].w;
    }

    dfs(1);

    ll ans = 0;
    for(auto x: mp[1]) ans += x.second;
    printf("%lld", ans);
}

Compilation message

magictree.cpp: In function 'bool nextRemove(int, int, ll)':
magictree.cpp:29:1: warning: no return statement in function returning non-void [-Wreturn-type]
   29 | }
      | ^
magictree.cpp: In function 'int main()':
magictree.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     scanf("%d %d %d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         scanf("%d", &par[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
magictree.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         scanf("%d %d %d", &v, &d, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

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

Subtask #2
0 / 3.0

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

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 16.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

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

Subtask #8
0 / 17.0

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