oj.uz

Submission #834336

# Submission time Handle Problem Language Result Execution time Memory
834336 2023-08-22T13:12:07 Z Essa2006 Magic Tree (CEOI19_magictree) C++14
6 / 100
 2000 ms 1048576 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
int n, m, k;
vector<int>P, Order;
vector<array<int, 2>>Q;
vector<vector<int>>A;
vector<map<int, int>>Has;

void pre(){
    P.clear(), Order.clear(), Q.clear(), A.clear(), Has.clear();
    P.resize(n+1), Q.resize(n+1), A.resize(n+1), Has.resize(n+1);
}

void dfs(int u){
    for(int i=0;i<A[u].size();i++){
        int v=A[u][i];
        if(v!=P[u])
            dfs(v);
    }
    Order.push_back(u);
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>k;
    pre();
    for(int i=2;i<=n;i++){
        cin>>P[i];
        int u=i, v=P[i];
        A[u].push_back(v);
        A[v].push_back(u);
    }
    for(int j=0;j<m;j++){
        int v, d, c;
        cin>>v>>d>>c;
        Q[v]={d, c};
    }
    dfs(1);
    for(int kk=0;kk<n;kk++){
        int u=Order[kk];
        for(int i=0;i<A[u].size();i++){
            int v=A[u][i];
            if(v==P[u])
                continue;
            map<int, int>New=Has[u];
            for(auto it2:Has[v]){
                int d=it2.FF, benf=it2.SS, mx_before=0;
                for(auto it:Has[u]){
                    if(it.FF>d){
                        New[it.FF]=max(New[it.FF], benf+it.SS);
                    }
                    else{
                        mx_before=max(mx_before, it.SS);
                    }
                }
                if(Has[u].count(d))
                    New[d]=max(Has[u][d], benf+mx_before);
                else
                    New[d]=benf+mx_before;
            }
            Has[u]=New;
        }
        if(Q[u][0]){
            map<int, int>New=Has[u];
            int d=Q[u][0], benf=Q[u][1], mx_before=0;
            for(auto it:Has[u]){
                if(it.FF>d){
                    break;
                }
                else{
                    mx_before=max(mx_before, it.SS);
                }
            }
            if(Has[u].count(d))
                New[d]=max(Has[u][d], benf+mx_before);
            else
                New[d]=benf+mx_before;
            Has[u]=New;
        }
    }
    int ans=0;
    for(auto it:Has[1]){
        ans=max(ans, it.SS);
    }
    cout<<ans<<endl;
}

Compilation message

magictree.cpp: In function 'void dfs(long long int)':
magictree.cpp:21:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i=0;i<A[u].size();i++){
      |                 ~^~~~~~~~~~~~
magictree.cpp: In function 'int main()':
magictree.cpp:46:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int i=0;i<A[u].size();i++){
      |                     ~^~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2077 ms 23728 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 12536 KB Output is correct
2 Correct 29 ms 13500 KB Output is correct
3 Correct 27 ms 12956 KB Output is correct
4 Execution timed out 2094 ms 588952 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

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

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Incorrect 148 ms 33868 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3664 KB Output is correct
2 Correct 50 ms 15412 KB Output is correct
3 Correct 51 ms 15368 KB Output is correct
4 Correct 54 ms 15572 KB Output is correct
5 Correct 1324 ms 15304 KB Output is correct
6 Correct 1341 ms 461016 KB Output is correct
7 Runtime error 1733 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 40 ms 12536 KB Output is correct
11 Correct 29 ms 13500 KB Output is correct
12 Correct 27 ms 12956 KB Output is correct
13 Execution timed out 2094 ms 588952 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Execution timed out 2077 ms 23728 KB Time limit exceeded
11 Halted 0 ms 0 KB -