oj.uz

Submission #282313

# Submission time Handle Problem Language Result Execution time Memory
282313 2020-08-24T09:43:51 Z infinite_iq Magic Tree (CEOI19_magictree) C++14
50 / 100
 2000 ms 793464 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][1001] ;
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 ;
        ll sum = 0 , z = 1;
        for ( int i = 0 ; i < m ; i ++ ) {
                int node , day , w ;
                cin >> node >> day >> w ;
                node -- , day -- ;
                fruit [node] = { w , day } ;
                s .ins ( day ) ;
                sum += w ;
                z &= ( v [node] .size () == 0 ) ;
        }
        if (z) {
                cout << sum << endl ;
                exit (0) ;
        }

        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 2816 KB Output is correct
3 Correct 2 ms 2816 KB Output is correct
4 Correct 3 ms 2816 KB Output is correct
5 Correct 2 ms 2816 KB Output is correct
6 Correct 2 ms 2816 KB Output is correct
7 Correct 2 ms 2816 KB Output is correct
8 Correct 2 ms 2816 KB Output is correct
9 Correct 2 ms 2816 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 8060 KB Output is correct
2 Correct 111 ms 7416 KB Output is correct
3 Correct 273 ms 10764 KB Output is correct
4 Correct 243 ms 9960 KB Output is correct
5 Correct 269 ms 10616 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9856 KB Output is correct
2 Correct 8 ms 9984 KB Output is correct
3 Correct 8 ms 9856 KB Output is correct
4 Execution timed out 2093 ms 74408 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 408836 KB Output is correct
2 Correct 449 ms 408184 KB Output is correct
3 Correct 434 ms 412792 KB Output is correct
4 Correct 374 ms 407400 KB Output is correct
5 Correct 404 ms 418168 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 2816 KB Output is correct
3 Correct 2 ms 2816 KB Output is correct
4 Correct 3 ms 2816 KB Output is correct
5 Correct 2 ms 2816 KB Output is correct
6 Correct 2 ms 2816 KB Output is correct
7 Correct 2 ms 2816 KB Output is correct
8 Correct 2 ms 2816 KB Output is correct
9 Correct 2 ms 2816 KB Output is correct
10 Correct 446 ms 422648 KB Output is correct
11 Correct 416 ms 414712 KB Output is correct
12 Correct 405 ms 426620 KB Output is correct
13 Correct 347 ms 421228 KB Output is correct
14 Correct 373 ms 431992 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 160248 KB Output is correct
2 Correct 889 ms 789920 KB Output is correct
3 Correct 897 ms 789752 KB Output is correct
4 Correct 1035 ms 790048 KB Output is correct
5 Correct 984 ms 788800 KB Output is correct
6 Correct 1000 ms 791276 KB Output is correct
7 Correct 955 ms 793464 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2816 KB Output is correct
3 Correct 2 ms 2816 KB Output is correct
4 Correct 3 ms 2816 KB Output is correct
5 Correct 2 ms 2816 KB Output is correct
6 Correct 2 ms 2816 KB Output is correct
7 Correct 2 ms 2816 KB Output is correct
8 Correct 2 ms 2816 KB Output is correct
9 Correct 2 ms 2816 KB Output is correct
10 Correct 9 ms 9856 KB Output is correct
11 Correct 8 ms 9984 KB Output is correct
12 Correct 8 ms 9856 KB Output is correct
13 Execution timed out 2093 ms 74408 KB Time limit exceeded
14 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 2816 KB Output is correct
3 Correct 2 ms 2816 KB Output is correct
4 Correct 3 ms 2816 KB Output is correct
5 Correct 2 ms 2816 KB Output is correct
6 Correct 2 ms 2816 KB Output is correct
7 Correct 2 ms 2816 KB Output is correct
8 Correct 2 ms 2816 KB Output is correct
9 Correct 2 ms 2816 KB Output is correct
10 Correct 123 ms 8060 KB Output is correct
11 Correct 111 ms 7416 KB Output is correct
12 Correct 273 ms 10764 KB Output is correct
13 Correct 243 ms 9960 KB Output is correct
14 Correct 269 ms 10616 KB Output is correct
15 Correct 9 ms 9856 KB Output is correct
16 Correct 8 ms 9984 KB Output is correct
17 Correct 8 ms 9856 KB Output is correct
18 Execution timed out 2093 ms 74408 KB Time limit exceeded
19 Halted 0 ms 0 KB -