oj.uz

Submission #282308

# Submission time Handle Problem Language Result Execution time Memory
282308 2020-08-24T09:35:23 Z infinite_iq Magic Tree (CEOI19_magictree) C++14
34 / 100
 262 ms 31224 KB 
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 340
#define mp make_pair
#define mid (l+r)/2
#define le node * 2 
#define ri node * 2 + 1 
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
#define all(x) x.begin(), x.end()
#define gc getchar_unlocked
typedef long long ll;
typedef short int si;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef pair<double,ll>pdi;
const ll inf=1e18;
const ll mod=998244353;
const ld Pi=acos(-1) ;
ll n , m , k ;
vll v [100009] ;
pll fruit [100009] ;
ll dp [100009][20] ;
unordered_map < int , int > id ;
void dfs ( int node ) {
        for ( auto u : v [node] ) {
                dfs ( u ) ;
                for ( int i = 0 ; i < k ; i ++ ) {
                        dp [node][i] += dp [u][i] ;
                }
        }
        dp [node][fruit[node] .se] += fruit[node] .fi ;
        for ( int i = 1 ; i < k ; i ++ ) {
                dp [node][i] = max ( dp [node][i] , dp [node][i-1] ) ;
        }
}
int main () {
        cin >> n >> m >> k ;
        for ( int i = 2 ; i <= n ; i ++ ) {
                int a , b = i ;
                cin >> a ;
                a -- , b -- ;
                v [a] .pb ( b ) ;
        }
        set < int > s ;
        for ( int i = 0 ; i < m ; i ++ ) {
                int node , day , w ;
                cin >> node >> day >> w ;
                node -- , day -- ;
                fruit [node] = { w , day } ;
                s .ins ( day ) ;
        }
        int N = 0 ;
        for ( auto u : s ) {
                id [u] = N ++ ;
        }
        for ( int i = 0 ; i < n ; i ++ ) {
                if ( fruit [i] .fi ) {
                        fruit [i] .se = id [fruit[i].se] ;
                }
        }
        k = N ;
        dfs ( 0 ) ;
        cout << dp [0][k-1] << endl ;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 150 ms 27768 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 22264 KB Output is correct
2 Correct 251 ms 22264 KB Output is correct
3 Correct 240 ms 26104 KB Output is correct
4 Correct 192 ms 21232 KB Output is correct
5 Correct 234 ms 31224 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 228 ms 22264 KB Output is correct
11 Correct 242 ms 22136 KB Output is correct
12 Correct 206 ms 25976 KB Output is correct
13 Correct 155 ms 21224 KB Output is correct
14 Correct 190 ms 31156 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

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

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Runtime error 150 ms 27768 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -