oj.uz

Submission #945777

# Submission time Handle Problem Language Result Execution time Memory
945777 2024-03-14T07:38:15 Z vjudge1 Magic Tree (CEOI19_magictree) C++17
6 / 100
 125 ms 176324 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 = 1005, mxc = 105, inf = 1e18, MX = 1e4 + 10;

int cost[MX][N], dp[MX][N];
vector <int> g[MX];
map <int,int> mp;

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});
	}
	sort(all(vp));
	int cur = 0, prev =  -1;
	for(auto &[a, b, c] : vp){
		if(a != prev)cur++;
		prev = a;
		a = cur;
		swap(a, b);
	}
	for(auto &[a, b, c] : vp){
		//cout << a <<"-"<< b <<"-"<< c << endl;
		cost[a][b] = c;
		swap(a, b);
	}
	for(int i = 1; i <= cur; i++){
		dfs(1, 1, i);
	}
	cout <<dp[1][cur];
}

Compilation message

magictree.cpp:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 | main(){
      | ^~~~
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 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4704 KB Output is correct
5 Correct 1 ms 4696 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4696 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct

Subtask #2
0 / 3.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18268 KB Output is correct
2 Correct 10 ms 18268 KB Output is correct
3 Correct 14 ms 18232 KB Output is correct
4 Runtime error 125 ms 176324 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

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

Subtask #5
0 / 16.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4704 KB Output is correct
5 Correct 1 ms 4696 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4696 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 10 ms 18268 KB Output is correct
11 Correct 10 ms 18268 KB Output is correct
12 Correct 14 ms 18232 KB Output is correct
13 Runtime error 125 ms 176324 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

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