oj.uz

Submission #945588

# Submission time Handle Problem Language Result Execution time Memory
945588 2024-03-14T05:19:17 Z vjudge1 Magic Tree (CEOI19_magictree) C++17
45 / 100
 230 ms 52240 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 = 1e5 + 100, mxc = 105, inf = 1e18, MX = 1e5 + 10, maxn = 1e5 + 10;

int cost[N][25], dp[N][25];

vector <int> g[N];


int t[N * 4], b[N * 4], used[N * 4];
int ar[N];
int n;
int s[maxn], p[maxn], tin[maxn], tout[maxn], depth[N];
int head[maxn]; // «голова» тяжелого пути, которому принадлежит v
int timer = 0;
 
void push(int v, int tl, int tr) {
	if(!used[v]) return;
	t[v] = max(t[v], b[v]);
	//cout << b[v] <<"->"<< tl << endl;
	if (tl != tr) {
		b[v * 2] = max(b[v * 2], b[v]);
		b[v * 2 + 1] = max(b[v * 2 + 1], b[v]);
		used[v*2+1]=1;
		used[v*2]=1;
	}
	used[v]=0;
}
 
void update(int l, int r, int x, int v = 1, int tl = 0, int tr = MX){
	push(v, tl, tr);
	if (tr < l || r < tl) return;
	if(l <= tl && tr <= r){
		b[v] = max(b[v], x);
		used[v]=1;
		push(v, tl, tr);
		return;
 	}else{	
		int mid=(tl+tr)/2;
		update(l, r, x,  v * 2, tl, mid);
		update(l, r, x,  v * 2 + 1, mid + 1, tr);
		t[v] = max(t[v * 2], t[v * 2 + 1]);
	}
}
 
int get(int l, int r, int v = 1, int tl = 0, int tr = MX){
	push(v, tl, tr);
	if (tr < l || tl > r) return  0;
	if(l <= tl && tr <= r){
		return t[v];
	} 
	int mid=(tl+tr)/2;
	return max(get(l, r, v * 2, tl, mid), get(l, r, v * 2 + 1, mid + 1, tr));	
}
 
void sizes(int v = 1, int par = 1) {
    s[v] = 1;
    for (int &u : g[v]) {
		if(u == par)continue;
		depth[u] = depth[v] + 1;
        sizes(u, v);
        s[v] += s[u];
        if (s[u] > s[g[v][0]]){
            // &u -- это ссылка, так что её легально использовать при swap-е
            swap(u, g[v][0]);
		}
    }
}
 
void hld(int v = 0, int par = 1) {
    tin[v] = timer++;
    p[v] = par;
    for (int u : g[v]) {
		if(u == par)continue;
        // если это тяжелый ребенок -- его next нужно передать
        // в противном случае он сам является головой нового пути
        head[u] = (u == g[v][0] ? head[v] : u);
        hld(u, v);
    }
    tout[v] = timer;
}
 
int ancestor(int a, int b) {
    return tin[a] <= tin[b] && tin[b] < tout[a];
}
 
void up(int &a, int &b, int x) {
    while (!ancestor(head[a], b)) {
        update(tin[head[a]], tin[a], x);
        a = p[head[a]];	
    }
}

void upupd(int a, int x) {
    int b = 1;
    up(a, b, x);
    up(b, a, x);
    if (!ancestor(a, b))
        swap(a, b);
    update(tin[a], tin[b], x);
}



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], 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);
	}
	if(k > 20){
		head[1] = 1;
		sizes(1);
		hld(1);
	}
	vector < array <int, 4> > vp;
	for(int i = 1 ; i<= m; i++){
		int a, b, c;
		cin >> a >> b >> c;
		vp.pb({b, -depth[a], a, c});
		if(k <= 20)
			cost[a][b] = c;
	}
	sort(all(vp));
	if(k > 20){
		for(auto &[time, dep, a, c] : vp){
			int sum = 0;
			for(auto to : g[a]){
				if(to != p[a])
				sum += get(tin[to], tin[to]);
			}
			upupd(a, sum + c);
		}
		int sum = 0;
		int a = 1;
		for(auto to : g[a]){
				//cout << to <<"-"<< get(tin[to], tin[to]) << endl;
				sum += get(tin[to], tin[to]);
			}
		for(int i = 1; i <= n; i++){
			//cout << get(tin[i], tin[i]) << endl;
		}
		cout << sum << endl;
	}else{
		for(int i = 1; i <= k; i++){
			dfs(1, 1, i);
		}
		cout << dp[1][k] << endl;
	}
}	
/*
 * Before implementing the problem:
	
	Do I understand the problem correctly?
	Which places are tricky? What do I need to remember to implement them correctly?
	Which place is the heaviest by implementation? Can I do it simpler?
	Which place is the slowest? Where do I need to be careful about constant factors and where I can choose slower but simpler implementation?
	----------------------------------
	If not AC:
 
	Did you remember to do everything to handle the tricky places you thought about before?
	Is the solution correct?
	Do I understand the problem correctly?
	----------------------------------
	If you have a test on which the solution gives wrong answer:
 
	Is the solution doing what it was supposed to do?
	Is the problem in the code or in the idea?
*/

Compilation message

magictree.cpp:133:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  133 | 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 1 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 20804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 74 ms 30344 KB Output is correct
5 Correct 72 ms 30888 KB Output is correct
6 Correct 151 ms 30424 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 49080 KB Output is correct
2 Correct 77 ms 48820 KB Output is correct
3 Correct 82 ms 51196 KB Output is correct
4 Correct 67 ms 49680 KB Output is correct
5 Correct 63 ms 52148 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 230 ms 48824 KB Output is correct
11 Correct 143 ms 48824 KB Output is correct
12 Correct 167 ms 50108 KB Output is correct
13 Correct 106 ms 49200 KB Output is correct
14 Correct 117 ms 52240 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 10844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 2 ms 8792 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 2 ms 8796 KB Output is correct
13 Correct 74 ms 30344 KB Output is correct
14 Correct 72 ms 30888 KB Output is correct
15 Correct 151 ms 30424 KB Output is correct
16 Correct 230 ms 48824 KB Output is correct
17 Correct 143 ms 48824 KB Output is correct
18 Correct 167 ms 50108 KB Output is correct
19 Correct 106 ms 49200 KB Output is correct
20 Correct 117 ms 52240 KB Output is correct
21 Incorrect 36 ms 10068 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Incorrect 77 ms 20804 KB Output isn't correct
11 Halted 0 ms 0 KB -