oj.uz

답안 #198120

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
198120 2020-01-24T18:19:32 Z model_code Magic Tree (CEOI19_magictree) C++17
0 / 100
 310 ms 26340 KB 
#include <bits/stdc++.h>
#define VERBOSE 1
using namespace std;

#define int long long

struct node
{
    bool fruit = false;
    int day,where,weight;
    vector<int> children;
    set<pair<int,int> > harvest;
};

vector<node> tree;

int depth(int v)
{
    int ans = 0;
    for(int c : tree[v].children)
        ans = max(ans,depth(c)+1);
    return ans;
}

// merge solutions in tree[from] and tree[in]
// merge from smaller set into larger
// return index of smaller set
int join_sol(int in,int from)
{
    if(tree[from].harvest.size() > tree[in].harvest.size())
        swap(in,from);

    for(auto it = tree[from].harvest.begin(); it!=tree[from].harvest.end();it++)
    {
        int day = it->first, add = it->second;
        auto inptr = tree[in].harvest.lower_bound({day,-1});
        if(inptr == tree[in].harvest.end() || inptr->first != day)
        {
            tree[in].harvest.insert({day,add});
        }
        else //(inptr->first == day)
        {
            pair<int,int> tmp = {inptr->first, inptr->second};
            tmp.second += add;
            tree[in].harvest.erase(inptr);
            tree[in].harvest.insert(tmp);
        }
    }
    return in;
}

void solve(int v)
{

    tree[v].where = v;
    tree[v].harvest.insert({-1,0});

    for(int c : tree[v].children)
    {
        solve(c);
        tree[v].where = join_sol(tree[v].where,tree[c].where);
    }

    int w = tree[v].where;

    if(tree[v].fruit)
    {
        auto it = tree[w].harvest.lower_bound({tree[v].day,-1});

        if(it == tree[w].harvest.end())
            tree[w].harvest.insert({ tree[v].day, tree[v].weight });
        else if( it->first == tree[v].day)
        {
            pair<int,int> newval = {it->first,it->second+tree[v].weight};
            tree[w].harvest.erase(it);
            it = tree[w].harvest.insert(newval).first;
            
            int debt = tree[v].weight;
            while(debt)
            {
                auto rn = it;
                rn++;
                if(rn == tree[w].harvest.end()) break;
                pair<int,int> tmp = {rn->first,rn->second};
                tree[w].harvest.erase(rn);
                int take = min(debt, tmp.second);
                debt -= take;
                tmp.second -= take;
                if(tmp.second)
                    tree[w].harvest.insert(tmp);
            }
        }
        else
        {
            it = tree[w].harvest.insert({tree[v].day, tree[v].weight}).first;
            int debt = tree[v].weight;
            while(debt)
            {
                auto rn = it;
                rn++;
                if(rn == tree[w].harvest.end()) break;
                pair<int,int> tmp = {rn->first,rn->second};
                tree[w].harvest.erase(rn);
                int take = min(debt, tmp.second);
                debt -= take;
                tmp.second -= take;
                if(tmp.second)
                    tree[w].harvest.insert(tmp);
            }
        }
    }

}

main()
{
    int n,m,k;
    cin >> n >> m >> k;

    tree.resize(n);

    for(int i=1;i<n;++i)
    {
        int parent;
        cin >> parent;
        parent--;
        tree[parent].children.push_back(i);
    }

    for(int i=0;i<m;++i)
    {
        int pos;
        cin >> pos;
        pos--;
        tree[pos].fruit = true;
        cin >> tree[pos].day >> tree[pos].weight;
    }

    solve(0);
    int ans = 0;
    for(auto it = tree[ tree[0].where ].harvest.begin(); it != tree[ tree[0].where ].harvest.end(); it++)
        ans += it->second;
    cout << ans << "\n";

    if(VERBOSE)
    {
        cerr <<  "depth " << depth(0) << "\n";
    }
}

Compilation message

magictree.cpp:115:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 235 ms 26340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 310 ms 22408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 4144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -