Submission #469401

#	Time	Username	Problem	Language	Result	Execution time	Memory
469401		kderylo	Magic Tree (CEOI19_magictree)	C++17	3 / 100	143 ms	20820 KiB

magictree

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int stala=131072;
vector<int>wektor[stala];
vector<pair<int,long long> >zbior[stala];
set<int>numery;
int czas[stala][2];
int jaki_wierzcholek[stala];
long long wartosc[stala];
long long tree[2*stala];
int ind;
void dfs(int k,int p)
{
    ind++;
    czas[k][0]=ind;
    jaki_wierzcholek[ind]=k;
    for(int i=0;i<(int)wektor[k].size();i++)
    {
        if(wektor[k][i]!=p)
        {
            dfs(wektor[k][i],k);
        }
    }
    czas[k][1]=ind;
}
void update(int index,long long war)
{
    index+=stala-1;
    tree[index]+=war;
    while(index>1)
    {
        index/=2;
        tree[index]=tree[2*index]+tree[(2*index)+1];
    }
}
long long query(int index,int index2)
{
    index+=stala-1;
    index2+=stala-1;
    long long res=tree[index];
    if(index!=index2)
    {
        res+=tree[index2];
    }
    while(index/2!=index2/2)
    {
        if(index%2==0)
        {
            res+=tree[index+1];
        }
        if(index2%2==1)
        {
            res+=tree[index2-1];
        }
        index/=2;
        index2/=2;
    }
    return res;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ile,owoce,dni;
    cin>>ile>>owoce>>dni;
    for(int i=2;i<=ile;i++)
    {
        int a;
        cin>>a;
        wektor[i].push_back(a);
        wektor[a].push_back(i);
    }
    ind=0;
    dfs(1,0);
    for(int i=1;i<=owoce;i++)
    {
        int wierzcholek,nr_dnia;
        long long cena;
        cin>>wierzcholek>>nr_dnia>>cena;
        wartosc[wierzcholek]=cena;
        zbior[nr_dnia].push_back(make_pair(czas[wierzcholek][0],cena));
    }
    for(int i=dni;i>=0;i--)
    {
        sort(zbior[i].begin(),zbior[i].end());
        for(int j=0;j<(int)zbior[i].size();j++)
        {
            int preorder=zbior[i][j].first;
            long long cena=zbior[i][j].second;
            int nr=jaki_wierzcholek[preorder];
            if(cena>query(czas[nr][0],czas[nr][1]))
            {
                while(!numery.empty())
                {
                    auto it=numery.lower_bound(czas[nr][0]);
                    if(it==numery.end())
                    {
                        break;
                    }
                    if(*it>czas[nr][1])
                    {
                        break;
                    }
                    int w=jaki_wierzcholek[*it];
                    update(czas[w][0],-wartosc[w]);
                    numery.erase(it);
                }
                numery.insert(czas[nr][0]);
                update(czas[nr][0],wartosc[nr]);
            }
        }
    }
    cout<<query(1,ile);

    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 3 / 3
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17