oj.uz

Submission #1100150

# Submission time Handle Problem Language Result Execution time Memory
1100150 2024-10-13T00:38:29 Z CpDark Roadside Advertisements (NOI17_roadsideadverts) C++17
100 / 100
 53 ms 12892 KB 
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vp;
typedef vector<vp> vvp;

vvp graph;

// LCA - Lowest common ancestor
struct LCA {
    vvi table; // table[v][i] = go up 2^i from v;
	vi timeIn;
    vi timeOut;
    vi upSum;
    int log;
	int timer;
	int n;

    void dfs(int v, int p, int sum) {
        upSum[v] = sum;
        timeIn[v] = timer;
		table[v][0] = p;
		timer++;

		for (int i = 0; i < graph[v].size(); i++) {
            int u = graph[v][i].first;
            int w = graph[v][i].second;
            if (u != p) dfs(u, v, sum + w);
		}

		timeOut[v] = timer;
		timer++;
	}

	void preCalc(int N, int root) {
		n = N;
		log = ceil(log2(n));
		timeIn.resize(n + 1);
		timeOut.resize(n + 1);
        table.resize(n + 1, vi(log + 1));
        upSum.resize(n + 1);
        timer = 0;

		dfs(root, root, 0);
		for (int i = 1; i <= log; i++) {
			for (int v = 1; v <= n; v++) {
				int p = table[v][i - 1];
				table[v][i] = table[p][i - 1];
			}
		}
	}

	bool isAncestor(int a, int b) { // Is a ancestor of b
		if (timeIn[a] <= timeIn[b] && timeOut[a] >= timeOut[b]) return true;
		return false;
	}

	int findLCA(int a, int b) {
		if (isAncestor(a, b)) return a;
		if (isAncestor(b, a)) return b;
		for (int i = log; i >= 0; i--) if (!isAncestor(table[a][i], b)) a = table[a][i];
		return table[a][0];
    }

    int LCA5(vector<int>& nodes) {  
        int ans = nodes[0];
        for (int i = 1; i < nodes.size(); i++) ans = findLCA(ans, nodes[i]);
        return ans;
    }
 
    int dist(int v, int u) {
        return upSum[v] + upSum[u] - 2 * upSum[findLCA(v, u)];
    }
};

LCA lca;
bool cmp(int v, int u) {
    return lca.timeIn[v] < lca.timeIn[u];
}


void init(int N, vector<int> V, vector<int> U, vector<int> W) {
    graph.resize(N);
    for (int i = 0;i < N - 1;i++) {
        graph[V[i]].push_back({ U[i],W[i] });
        graph[U[i]].push_back({ V[i],W[i] });
    }
    lca.preCalc(N, 0);
}


int query(int a, int b, int c, int d, int e) {
    vi nodes = { a,b,c,d,e };
    sort(nodes.begin(), nodes.end(), cmp);
    
    int root = lca.LCA5(nodes);
	int ans = lca.dist(root, nodes[0]);
	for (int i = 1; i < 5; i++) ans += lca.dist(nodes[i], lca.findLCA(nodes[i - 1], nodes[i]));
 
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N;

    vi V(N - 1), U(N - 1), W(N - 1);
    for (int i = 0;i < N - 1;i++)cin >> V[i] >> U[i] >> W[i];
    
    init(N, V, U, W);

    cin >> Q;
    for (int i = 0;i < Q;i++) {
        int a, b, c, d, e;
        cin >> a >> b >> c >> d >> e;
        cout << query(a, b, c, d, e) << endl;
    }
    return 0;
}

Compilation message

roadsideadverts.cpp: In member function 'void LCA::dfs(int, int, int)':
roadsideadverts.cpp:27:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for (int i = 0; i < graph[v].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
roadsideadverts.cpp: In member function 'int LCA::LCA5(std::vector<int>&)':
roadsideadverts.cpp:69:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for (int i = 1; i < nodes.size(); i++) ans = findLCA(ans, nodes[i]);
      |                         ~~^~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 11832 KB Output is correct
2 Correct 41 ms 12624 KB Output is correct
3 Correct 40 ms 12888 KB Output is correct
4 Correct 39 ms 12892 KB Output is correct
5 Correct 46 ms 12888 KB Output is correct
6 Correct 42 ms 12892 KB Output is correct
7 Correct 42 ms 12636 KB Output is correct
8 Correct 40 ms 12624 KB Output is correct
9 Correct 40 ms 12860 KB Output is correct
10 Correct 42 ms 12636 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 11096 KB Output is correct
2 Correct 25 ms 12364 KB Output is correct
3 Correct 32 ms 12408 KB Output is correct
4 Correct 27 ms 12368 KB Output is correct
5 Correct 33 ms 12328 KB Output is correct
6 Correct 27 ms 12380 KB Output is correct
7 Correct 26 ms 12432 KB Output is correct
8 Correct 27 ms 12416 KB Output is correct
9 Correct 26 ms 12380 KB Output is correct
10 Correct 26 ms 12372 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 52 ms 11832 KB Output is correct
3 Correct 41 ms 12624 KB Output is correct
4 Correct 40 ms 12888 KB Output is correct
5 Correct 39 ms 12892 KB Output is correct
6 Correct 46 ms 12888 KB Output is correct
7 Correct 42 ms 12892 KB Output is correct
8 Correct 42 ms 12636 KB Output is correct
9 Correct 40 ms 12624 KB Output is correct
10 Correct 40 ms 12860 KB Output is correct
11 Correct 42 ms 12636 KB Output is correct
12 Correct 22 ms 11096 KB Output is correct
13 Correct 25 ms 12364 KB Output is correct
14 Correct 32 ms 12408 KB Output is correct
15 Correct 27 ms 12368 KB Output is correct
16 Correct 33 ms 12328 KB Output is correct
17 Correct 27 ms 12380 KB Output is correct
18 Correct 26 ms 12432 KB Output is correct
19 Correct 27 ms 12416 KB Output is correct
20 Correct 26 ms 12380 KB Output is correct
21 Correct 26 ms 12372 KB Output is correct
22 Correct 42 ms 11864 KB Output is correct
23 Correct 41 ms 11100 KB Output is correct
24 Correct 40 ms 12632 KB Output is correct
25 Correct 40 ms 12636 KB Output is correct
26 Correct 40 ms 12636 KB Output is correct
27 Correct 41 ms 12636 KB Output is correct
28 Correct 53 ms 12628 KB Output is correct
29 Correct 41 ms 12440 KB Output is correct
30 Correct 40 ms 12464 KB Output is correct
31 Correct 39 ms 12628 KB Output is correct