Submission #945588

#	Time	Username	Problem	Language	Result	Execution time	Memory
945588		vjudge1	Magic Tree (CEOI19_magictree)	C++17	45 / 100	230 ms	52240 KiB

magictree

#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 (stderr)

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 / 6
• Subtask 2: 0 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17