oj.uz

Submission #469401

# Submission time Handle Problem Language Result Execution time Memory
469401 2021-08-31T21:29:04 Z kderylo Magic Tree (CEOI19_magictree) C++17
3 / 100
 143 ms 20820 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Incorrect 4 ms 6476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 15104 KB Output is correct
2 Correct 50 ms 15372 KB Output is correct
3 Correct 143 ms 20340 KB Output is correct
4 Correct 138 ms 20220 KB Output is correct
5 Correct 136 ms 20820 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 109 ms 18144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Incorrect 4 ms 6476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7864 KB Output is correct
2 Correct 40 ms 13780 KB Output is correct
3 Correct 43 ms 13876 KB Output is correct
4 Correct 42 ms 13804 KB Output is correct
5 Correct 21 ms 13764 KB Output is correct
6 Incorrect 40 ms 14736 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Incorrect 4 ms 6476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Incorrect 4 ms 6476 KB Output isn't correct
3 Halted 0 ms 0 KB -