Submission #1100143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100143		CpDark	Roadside Advertisements (NOI17_roadsideadverts)	C++17	100 / 100	60 ms	15828 KiB

roadsideadverts

#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 {
    vvp table;
    vi timeIn;
    vi timeOut;
    vi depth;
    int log;
	int timer;
	int n;

    void dfs(int v, int p, int d, int w) {
        depth[v] = d;
        timeIn[v] = timer;
        table[v][0] = { p, w };
		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, d + 1, 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);
        depth.resize(n + 1);
        table.resize(n + 1, vp(log + 1));
		timer = 0;

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

	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].first, b)) a = table[a][i].first;
		return table[a][0].first;
    }

    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 subsequentPathSum(int v, int u) {
        if (depth[v] < depth[u]) swap(v, u);
    
        int diff = depth[v] - depth[u];
        int sum = 0;
        for (int i = 0; i <= log; i++) {
			if ((diff >> i) & 1) sum += table[v][i].second, v = table[v][i].first;
			if (v == -1) return -1;
		}
        return sum;
    }
};

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.subsequentPathSum(root, nodes[0]);
	for (int i = 1; i < 5; i++) ans += lca.subsequentPathSum(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 (stderr)

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

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