oj.uz

Submission #898987

# Submission time Handle Problem Language Result Execution time Memory
898987 2024-01-05T10:32:59 Z alexdd Magic Tree (CEOI19_magictree) C++17
47 / 100
 2000 ms 294416 KB 
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
const int maxn = 1e5;
int n,m,k;
int parent[maxn+5];
int w[maxn+5];
int day[maxn+5];
vector<int> con[maxn+5];

vector<pair<int,long long>> rez[maxn+5];///{zi,suc}

long long getrez(int nod, int zi)
{
    if(rez[nod].empty())
        return 0;
    pair<int,long long> aux = {zi,INF};
    auto it = lower_bound(rez[nod].begin(),rez[nod].end(),aux);
    if(it==rez[nod].begin())
        return 0;
    it--;
    pair<int,long long> cop = *it;
    return cop.second;
}

void dfs(int nod)
{
    map<int,int> calc;
    for(auto adj:con[nod])
    {
        dfs(adj);
        for(auto x:rez[adj])
            calc[x.first]++;
    }
    if(day[nod]!=0) calc[day[nod]]++;
    long long mxm=0;
    for(auto it:calc)
    {
        pair<int,long long> aux = {it.first, 0};
        if(aux.first == day[nod])
            aux.second += w[nod];
        for(auto adj:con[nod])
        {
            aux.second += getrez(adj, aux.first);
        }
        if(aux.second > mxm)
        {
            mxm = aux.second;
            rez[nod].push_back(aux);
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>k;
    for(int i=2;i<=n;i++)
    {
        cin>>parent[i];
        con[parent[i]].push_back(i);
    }
    int a;
    for(int i=1;i<=m;i++)
    {
        cin>>a;
        cin>>day[a]>>w[a];
    }
    dfs(1);
    cout<<rez[1].back().second;
    return 0;
}
/**


*/

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 15332 KB Output is correct
2 Execution timed out 2063 ms 289480 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5464 KB Output is correct
2 Correct 3 ms 5980 KB Output is correct
3 Correct 20 ms 9820 KB Output is correct
4 Correct 88 ms 42548 KB Output is correct
5 Execution timed out 2097 ms 294416 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 11344 KB Output is correct
2 Correct 40 ms 10832 KB Output is correct
3 Correct 51 ms 21072 KB Output is correct
4 Correct 31 ms 9436 KB Output is correct
5 Correct 57 ms 34244 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 1 ms 4952 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 1 ms 4952 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 87 ms 14020 KB Output is correct
11 Correct 69 ms 13140 KB Output is correct
12 Correct 160 ms 57292 KB Output is correct
13 Correct 43 ms 9432 KB Output is correct
14 Correct 176 ms 80216 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5720 KB Output is correct
2 Correct 17 ms 8028 KB Output is correct
3 Correct 17 ms 8028 KB Output is correct
4 Correct 19 ms 8084 KB Output is correct
5 Correct 211 ms 6616 KB Output is correct
6 Correct 448 ms 105936 KB Output is correct
7 Correct 400 ms 119888 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 1 ms 4952 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 1 ms 4952 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 2 ms 5464 KB Output is correct
11 Correct 3 ms 5980 KB Output is correct
12 Correct 20 ms 9820 KB Output is correct
13 Correct 88 ms 42548 KB Output is correct
14 Execution timed out 2097 ms 294416 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 1 ms 4952 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 1 ms 4952 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 118 ms 15332 KB Output is correct
11 Execution timed out 2063 ms 289480 KB Time limit exceeded
12 Halted 0 ms 0 KB -