oj.uz

Submission #834419

# Submission time Handle Problem Language Result Execution time Memory
834419 2023-08-22T14:06:00 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(auto v:A[u]){
            if(v==P[u])
                continue;
            map<int, int>New=Has[u];
            for(auto it2:Has[v]){
                int d=it2.FF, benf=it2.SS, mx=0;
                for(auto it:Has[u]){
                    if(it.FF>d)
                        New[it.FF]=max(New[it.FF], it.SS+benf);
                    else
                        mx=max(mx, it.SS);
                }
                if(Has[u].find(d)!=Has[u].end())
                    New[d]=max(Has[u][d], benf+mx);
                else
                    New[d]=benf+mx;
            }
            Has[u]=New;
        }
        if(Q[u][0]){
            int d=Q[u][0], benf=Q[u][1], mx=0;
            for(auto it:Has[u]){
                if(it.FF>d)
                    break;
                mx=max(mx, it.SS);
            }
            Has[u][d]=max(Has[u][d], benf+mx);
        }
    }
    int ans=0;
    for(auto it:Has[1])
        ans=max(ans, it.SS);
    cout<<ans;


}

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++){
      |                 ~^~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 260 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 2021 ms 22636 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 12500 KB Output is correct
2 Correct 37 ms 13504 KB Output is correct
3 Correct 23 ms 12884 KB Output is correct
4 Execution timed out 2101 ms 863868 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

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

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 260 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 173 ms 32536 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 3568 KB Output is correct
2 Correct 40 ms 14912 KB Output is correct
3 Correct 69 ms 14956 KB Output is correct
4 Correct 49 ms 14980 KB Output is correct
5 Correct 1462 ms 15176 KB Output is correct
6 Correct 1390 ms 460336 KB Output is correct
7 Runtime error 1798 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 260 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 24 ms 12500 KB Output is correct
11 Correct 37 ms 13504 KB Output is correct
12 Correct 23 ms 12884 KB Output is correct
13 Execution timed out 2101 ms 863868 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 260 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 2021 ms 22636 KB Time limit exceeded
11 Halted 0 ms 0 KB -