제출 #336064

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
336064		saniyar_krmi	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	30 ms	29036 KiB

commuter_pass

// YOU ONLY GOT ONE SHOT
#include <bits/stdc++.h>
#define put(x) cerr << #x << ": " << x << '\n'
#define line() cerr << "**************\n"

//#define F first
//#define S second
//#define mul(x, y) (((x) * (y)) %mod)
#define bit(i, j) (((i)>>(j)) &1)
//#define left(id) ((id<<1) + 1)
//#define right(id) ((id<<1) + 2)
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;

const int maxn = 2e5 + 10, lg = 21;
int n, m;
vector <int> G[maxn];
vector <piii> edge[maxn];

ll dp[maxn], sp[maxn][lg], sum[maxn];

int h[maxn], up[maxn][lg];
int st[maxn], ft[maxn], T;
vector <int> vec[maxn];

void dfs1(int v, int par){
	st[v] = T++;
	h[v] = h[par] + 1;
	up[v][0] = par;
	for(int i=1; i<lg; i++)
		up[v][i] = up[up[v][i-1]][i-1];

	for(int u: G[v]){
		if(u == par)
			continue;
		dfs1(u, v);
	}
	ft[v] = T;
	vec[h[v]].push_back(ft[v]);
}

void dfs(int v, int par){
	for(int u: G[v])
		sum[v] += sum[u];
}

int lift(int u, int p){
	for(int i=lg-1; i>=0; i--)
		if(bit(p, i))
			u = up[u][i];
	return u;
}

int get(int u, int v){
	if(h[u] < h[v]) swap(u, v);
	u = lift(u, h[u] - h[v]);
	if(u == v) return u;
	for(int i=lg-1; i>=0; i--)
		if(up[u][i] != up[v][i])
			u = up[u][i], v = up[v][i];
	return up[u][0];
}

int main(){
//	ios_base::sync_with_stdio(false);
//	cin.tie(0);  cout.tie(0);

	cin >> n >> m;
	int pi;
	for(int i=2; i<=n; i++){
		cin >> pi;
		G[i].push_back(pi), G[pi].push_back(i);
	}

	h[0] = -1;
	dfs1(1, 0);

	int u, v, c;
	for(int i=0; i<m; i++){
		cin >> u >> v >> c;
		int lca = get(u, v);
		edge[lca].push_back({{u, v}, c});
	}

	dfs(1, 0);

	cout << dp[1] << '\n';
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45