oj.uz

Submission #898983

# Submission time Handle Problem Language Result Execution time Memory
898983 2024-01-05T10:31:29 Z alexdd Magic Tree (CEOI19_magictree) C++17
47 / 100
 2000 ms 292776 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int 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,int>> rez[maxn+5];///{zi,suc}

int getrez(int nod, int zi)
{
    if(rez[nod].empty())
        return 0;
    pair<int,int> aux = {zi,INF};
    auto it = lower_bound(rez[nod].begin(),rez[nod].end(),aux);
    if(it==rez[nod].begin())
        return 0;
    it--;
    pair<int,int> 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]]++;
    int mxm=0;
    for(auto it:calc)
    {
        pair<int,int> 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()
{
    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 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 7016 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 1 ms 6756 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 18256 KB Output is correct
2 Execution timed out 2048 ms 292776 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 7004 KB Output is correct
2 Correct 4 ms 7516 KB Output is correct
3 Correct 24 ms 11540 KB Output is correct
4 Correct 151 ms 45632 KB Output is correct
5 Execution timed out 2055 ms 290352 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 14680 KB Output is correct
2 Correct 103 ms 14312 KB Output is correct
3 Correct 103 ms 24488 KB Output is correct
4 Correct 77 ms 12740 KB Output is correct
5 Correct 130 ms 37584 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 7016 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 1 ms 6756 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Correct 117 ms 16896 KB Output is correct
11 Correct 112 ms 15988 KB Output is correct
12 Correct 209 ms 60044 KB Output is correct
13 Correct 77 ms 11968 KB Output is correct
14 Correct 219 ms 82840 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7512 KB Output is correct
2 Correct 35 ms 10052 KB Output is correct
3 Correct 33 ms 10024 KB Output is correct
4 Correct 32 ms 10068 KB Output is correct
5 Correct 248 ms 8604 KB Output is correct
6 Correct 466 ms 108116 KB Output is correct
7 Correct 389 ms 121796 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 7016 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 1 ms 6756 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Correct 2 ms 7004 KB Output is correct
11 Correct 4 ms 7516 KB Output is correct
12 Correct 24 ms 11540 KB Output is correct
13 Correct 151 ms 45632 KB Output is correct
14 Execution timed out 2055 ms 290352 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 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 7016 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 1 ms 6756 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Correct 138 ms 18256 KB Output is correct
11 Execution timed out 2048 ms 292776 KB Time limit exceeded
12 Halted 0 ms 0 KB -