oj.uz

Submission #945772

# Submission time Handle Problem Language Result Execution time Memory
945772 2024-03-14T07:33:47 Z vjudge1 Magic Tree (CEOI19_magictree) C++17
6 / 100
 693 ms 1048576 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#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 = 1e5 + 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]);
	//cout << v <<" "<< time <<" "<< dp[v][time] << endl;
}

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] << endl;
}

Compilation message

magictree.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   39 | main(){
      | ^~~~
magictree.cpp: In function 'void fp(std::string)':
magictree.cpp:15:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 | void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:15:70: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 | 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 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct
8 Correct 2 ms 6748 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 226 ms 799692 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 12 ms 20316 KB Output is correct
2 Correct 13 ms 20312 KB Output is correct
3 Correct 10 ms 20312 KB Output is correct
4 Runtime error 132 ms 801992 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 240 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

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

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 693 ms 321240 KB Output is correct
2 Runtime error 244 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Correct 12 ms 20316 KB Output is correct
11 Correct 13 ms 20312 KB Output is correct
12 Correct 10 ms 20312 KB Output is correct
13 Runtime error 132 ms 801992 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 2 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Runtime error 226 ms 799692 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -