oj.uz

Submission #945792

# Submission time Handle Problem Language Result Execution time Memory
945792 2024-03-14T07:47:53 Z vjudge1 Magic Tree (CEOI19_magictree) C++11
34 / 100
 2000 ms 98956 KB 
#include <bits/stdc++.h>
 
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
#define rnd(l, r) uniform_int_distribution<int>(l, r)(rng)
 
using namespace std;
 
void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);} 
int pow(int a,int b,int m){int ans=1;while(b){if(b&1){ans=(ans*a)%m;}b>>=1;a=(a*a)%m;}return ans;}
int binpow(int a,int b){int ans=1;while(b){if(b&1){ans=(ans*a);}b>>=1;a=(a*a);}return ans;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int N = 50, mxc = 105, inf = 1e18, MX = 1e5 + 10;

int cost[MX][N], dp[MX][N];
vector <int> g[MX];
void dfs(int v = 1, int par = 1, int time = 1){
	dp[v][time] = max(dp[v][time - 1], cost[v][time]);
	int sum = 0;
	for(auto to : g[v]){
		if(to == par)continue;
		dfs(to, v, time);
		sum += dp[to][time];
		dp[v][time] = max(dp[v][time], dp[to][time] + cost[v][time]);
	}
	dp[v][time] = max(dp[v][time], sum + cost[v][time]);
}

main(){
	iostream::sync_with_stdio(false);	
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    for(int i = 2; i <= n; i++){
		int a;
		cin >> a;
		g[a].pb(i);
		g[i].pb(a);
	}
	vector < array <int, 3> > vp;
	for(int i = 1 ; i<= m; i++){
		int a, b, c;
		cin >> a >> b >> c;
		vp.pb({b, a, c});
	}
	for(auto &[a, b, c] : vp){
		swap(a, b);
		//cout << a <<"-"<< b <<"-"<< c << endl;
		cost[a][b] = c;
		swap(a, b);
	}
	for(int i = 1; i <= k; i++){
		dfs(1, 1, i);
	}
	cout <<dp[1][k];
}

Compilation message

magictree.cpp:34:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   34 | main(){
      | ^~~~
magictree.cpp: In function 'int main()':
magictree.cpp:52:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |  for(auto &[a, b, c] : vp){
      |            ^
magictree.cpp: In function 'void fp(std::string)':
magictree.cpp:13:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:13:70: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 64 ms 98956 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 15 ms 6748 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 92 ms 89536 KB Output is correct
2 Correct 79 ms 89196 KB Output is correct
3 Correct 73 ms 93048 KB Output is correct
4 Correct 59 ms 89528 KB Output is correct
5 Correct 69 ms 97828 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6756 KB Output is correct
5 Correct 1 ms 6804 KB Output is correct
6 Correct 2 ms 6808 KB Output is correct
7 Correct 1 ms 6756 KB Output is correct
8 Correct 1 ms 6756 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Correct 320 ms 89328 KB Output is correct
11 Correct 182 ms 88308 KB Output is correct
12 Correct 226 ms 92056 KB Output is correct
13 Correct 128 ms 89136 KB Output is correct
14 Correct 155 ms 97724 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6756 KB Output is correct
5 Correct 1 ms 6804 KB Output is correct
6 Correct 2 ms 6808 KB Output is correct
7 Correct 1 ms 6756 KB Output is correct
8 Correct 1 ms 6756 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Incorrect 15 ms 6748 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 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6756 KB Output is correct
5 Correct 1 ms 6804 KB Output is correct
6 Correct 2 ms 6808 KB Output is correct
7 Correct 1 ms 6756 KB Output is correct
8 Correct 1 ms 6756 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Runtime error 64 ms 98956 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -