oj.uz

답안 #834408

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
834408 2023-08-22T14:02:06 Z Essa2006 Magic Tree (CEOI19_magictree) C++17
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].count(d))
                    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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2029 ms 22760 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 12500 KB Output is correct
2 Correct 33 ms 13604 KB Output is correct
3 Correct 26 ms 12884 KB Output is correct
4 Execution timed out 2095 ms 917624 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 82 ms 22464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 155 ms 32636 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 3808 KB Output is correct
2 Correct 65 ms 15020 KB Output is correct
3 Correct 74 ms 14960 KB Output is correct
4 Correct 82 ms 15108 KB Output is correct
5 Correct 1541 ms 15304 KB Output is correct
6 Correct 1494 ms 460572 KB Output is correct
7 Runtime error 1864 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 23 ms 12500 KB Output is correct
11 Correct 33 ms 13604 KB Output is correct
12 Correct 26 ms 12884 KB Output is correct
13 Execution timed out 2095 ms 917624 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Execution timed out 2029 ms 22760 KB Time limit exceeded
11 Halted 0 ms 0 KB -