oj.uz

Submission #517114

# Submission time Handle Problem Language Result Execution time Memory
517114 2022-01-22T14:45:57 Z tzuyuna Roadside Advertisements (NOI17_roadsideadverts) C++14
100 / 100
 137 ms 16212 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9676 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 14716 KB Output is correct
2 Correct 88 ms 16120 KB Output is correct
3 Correct 104 ms 16108 KB Output is correct
4 Correct 92 ms 16068 KB Output is correct
5 Correct 96 ms 16212 KB Output is correct
6 Correct 98 ms 16016 KB Output is correct
7 Correct 89 ms 16016 KB Output is correct
8 Correct 93 ms 16092 KB Output is correct
9 Correct 100 ms 16076 KB Output is correct
10 Correct 93 ms 16020 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 12880 KB Output is correct
2 Correct 40 ms 15244 KB Output is correct
3 Correct 39 ms 15348 KB Output is correct
4 Correct 35 ms 15240 KB Output is correct
5 Correct 34 ms 15208 KB Output is correct
6 Correct 49 ms 15232 KB Output is correct
7 Correct 38 ms 15220 KB Output is correct
8 Correct 35 ms 15176 KB Output is correct
9 Correct 38 ms 15236 KB Output is correct
10 Correct 38 ms 15300 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9676 KB Output is correct
2 Correct 124 ms 14716 KB Output is correct
3 Correct 88 ms 16120 KB Output is correct
4 Correct 104 ms 16108 KB Output is correct
5 Correct 92 ms 16068 KB Output is correct
6 Correct 96 ms 16212 KB Output is correct
7 Correct 98 ms 16016 KB Output is correct
8 Correct 89 ms 16016 KB Output is correct
9 Correct 93 ms 16092 KB Output is correct
10 Correct 100 ms 16076 KB Output is correct
11 Correct 93 ms 16020 KB Output is correct
12 Correct 29 ms 12880 KB Output is correct
13 Correct 40 ms 15244 KB Output is correct
14 Correct 39 ms 15348 KB Output is correct
15 Correct 35 ms 15240 KB Output is correct
16 Correct 34 ms 15208 KB Output is correct
17 Correct 49 ms 15232 KB Output is correct
18 Correct 38 ms 15220 KB Output is correct
19 Correct 35 ms 15176 KB Output is correct
20 Correct 38 ms 15236 KB Output is correct
21 Correct 38 ms 15300 KB Output is correct
22 Correct 116 ms 14572 KB Output is correct
23 Correct 137 ms 13284 KB Output is correct
24 Correct 133 ms 15636 KB Output is correct
25 Correct 104 ms 15528 KB Output is correct
26 Correct 105 ms 15536 KB Output is correct
27 Correct 112 ms 15620 KB Output is correct
28 Correct 108 ms 15616 KB Output is correct
29 Correct 121 ms 15632 KB Output is correct
30 Correct 115 ms 15600 KB Output is correct
31 Correct 111 ms 15608 KB Output is correct