Submission #517114

#	Time	Username	Problem	Language	Result	Execution time	Memory
517114		tzuyuna	Roadside Advertisements (NOI17_roadsideadverts)	C++14	100 / 100	137 ms	16212 KiB

roadsideadverts

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define si second
#define ll long long 
typedef pair<int,int> pi;

struct edge {
	int u, v, c;
};

const int mxn = 100005;	
int N, Q; 
int dist[mxn], twok[mxn][18], depth[mxn], par[mxn];
vector<pi> adj[mxn];

void dfs(int x, int p, int d, long long wd) {
	depth[x] = d;
	dist[x] = wd;
	twok[x][0] = p;
	for (int i = 1; i <= 17; i++) {
		if (twok[x][i - 1] == -1) break;
		twok[x][i] = twok[twok[x][i - 1]][i - 1];
	}
	for (auto it: adj[x]) {
		if (it.first != p) dfs(it.first,x,d+1,wd+it.second);
	}
}
int kth_parent(int x, int k){
    for (int i = 0; i <= 17; i++){
        if (k & (1 << i)) x = twok[x][i];
        if (x <= -1) return -1;
    }
    return x;
}
int lca(int x, int y){
    if (depth[x] > depth[y]) {
        int dd = depth[x] - depth[y];
        x = kth_parent(x, dd);
    } else {
        int dd = depth[y] - depth[x];
        y = kth_parent(y, dd);
    }
    if (x == y) return x;
    for (int i = 17; i >= 0; i--){
        if (twok[x][i] != twok[y][i]){
            x = twok[x][i];
            y = twok[y][i];
        }
    }
    return twok[x][0];
}

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

int root(int x) {
    if (par[x] == x) return x;
    return par[x] = root(par[x]);
}
bool same(int x, int y) {return root(x) == root(y);}
void merge(int x, int y) {
    x = root(x), y = root(y);
    if (x == y) return;
    par[x] = y; 
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].pb({b, c});
		adj[b].pb({a, c});
	}
	memset(twok, -1, sizeof twok);
	dfs(0, -1, 0, 0);
	cin >> Q;
	while (Q--) {
		vector<int> nodes(5); 
		set<int> chk;
		vector<edge> edges;
		for (int i = 0; i < 5; ++i) cin >> nodes[i];
		for (int i = 0; i < 4; ++i) {
			for (int j = i + 1; j < 5; ++j) {
				chk.insert(lca(nodes[i], nodes[j]));
			}
		}
		for (int i = 0; i < 5; ++i) chk.insert(nodes[i]);
		for (auto i: chk) {
			par[i] = i;
			for (auto j: chk) if (i != j) {
				int d = mindist(i, j);
				edges.pb({i, j, d});
			}
		}
		sort(edges.begin(), edges.end(), [](edge a, edge b) {
			return a.c < b.c;
		});
		int ans = 0;
		for (auto i: edges) {
			if (!same(i.u, i.v)) {
				merge(i.u, i.v);
				ans += i.c;
			}
		}
		cout << ans << '\n'; 
	}
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 40 / 40
• Subtask 4: 30 / 30