oj.uz

답안 #945792

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

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

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

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

Subtask #7
0 / 22.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -