Submission #983122

#	Time	Username	Problem	Language	Result	Execution time	Memory
983122		vjudge1	Cyberland (APIO23_cyberland)	C++17	0 / 100	3109 ms	1015300 KiB

cyberland

#include <bits/stdc++.h>
using namespace std;

const long long NMAX = 1e5 + 5;
vector<pair<long long,long long> > g[NMAX];
vector<long long> dis(NMAX);
vector<vector<long long> > up(20, vector<long long>(NMAX));
vector<long long> ary(NMAX), tin(NMAX), tout(NMAX);
long long ans, goal, timer;

void precalc(long long v, long long p){
	tin[v] = ++timer;
	up[0][v] = p;
	for(long long i = 1; i < 20; i++){
		up[i][v] = up[i - 1][up[i - 1][v]];
	}
	for(auto [to, cost] : g[v]){
		if(to != p){
			dis[to] = dis[v] + cost;
			precalc(to, v);
		}
	}
	tout[v] = ++timer;	
}

bool upper (long long a, long long b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

long long lca (long long a, long long b) {
	if (upper (a, b))  return a;
	if (upper (b, a))  return b;
	for (long long i=19; i>=0; --i)
		if (! upper (up[a][i], b))
			a = up[a][i];
	return up[a][0];
}

long long dist(long long a, long long b){
	return dis[a] + dis[b] - dis[lca(a, b)] * 2;
}

void dfs(long long v, long long p){
	if(v == goal) return;
	if(ary[v] == 0){
		ans = min(ans, dist(v, goal));
	}
	for(auto [to, cost] : g[v]){
		if(to != p) dfs(to, v);
	}
}

double solve(int n, int m, int k, int h, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
	for(long long i = 1; i <= n; i++){
		g[i].clear();
		dis[i] = 0;
		for(long long j = 0; j < 20; j++) up[j][i] = 0;
		tin[i] = 0;
		tout[i] = 0;
		timer = 0;
	}
	
	goal = h;
    for(long long i = 0; i < m; i++){
		g[x[i]].push_back({y[i], c[i]});
		g[y[i]].push_back({x[i], c[i]});
	}
	for(long long i = 0; i < n; i++){
		ary[i + 1] = arr[i];
	}
	precalc(1, 1);
	ans = dist(1, goal);
	dfs(1, -1);
	
	return ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3