oj.uz

Submission #1100149

# Submission time Handle Problem Language Result Execution time Memory
1100149 2024-10-13T00:35:08 Z CpDark Roadside Advertisements (NOI17_roadsideadverts) C++17
100 / 100
 73 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;

struct DSU {
	vi par, subSize;
	int size;

    DSU() {}

	void init(int n) {
        size = n;
        par.clear();
        subSize.clear();
        par.resize(n);
		subSize.resize(n, 1);
		for (int i = 0; i < n; i++) par[i] = i;
	}

	int findSet(int v) {
		if (v == par[v]) return v;
		par[v] = findSet(par[v]);
		return par[v];
	}

	bool unite(int v, int u) {
		int pv = findSet(v);
		int pu = findSet(u);
		if (pu == pv) return false;

		if (subSize[pu] < subSize[pv]) swap(pv, pu);
		
		par[pv] = pu;
		subSize[pu] += subSize[pv];
		return true;
	}
};

// MST - Minimum spanning tree, Kruskal's algorithm
struct MST {
	int cost = 0;

	DSU dsu;
	int findMST(vector<pair<int, pii>>& edges, int n) {
		dsu.init(n);
		sort(edges.begin(), edges.end());

        int counter = 0;
        cost = 0;        
        for (int i = 0;i < edges.size();i++) {
            if (counter == n - 1)break;
            int a = edges[i].second.first;
			int b = edges[i].second.second;
			int w = edges[i].first;
			if (dsu.unite(a, b)) cost += w;
		}

		return cost;
	}
};


// 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 dist(int v, int u) {
        return upSum[v] + upSum[u] - 2 * upSum[findLCA(v, u)];
    }

};


LCA lca;

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);
}

MST mst;
int query(int a, int b, int c, int d, int e) {
    vi nodes = { a,b,c,d,e };
    vi newVertices;
    for (int i = 0;i < nodes.size();i++) {
        for (int j = i;j < nodes.size();j++) {
            newVertices.push_back(lca.findLCA(nodes[i], nodes[j]));
        } 
    }
    sort(newVertices.begin(), newVertices.end());
    newVertices.erase( unique( newVertices.begin(), newVertices.end() ), newVertices.end() );

    vvp newGraph(newVertices.size());
    vector<pair<int, pii>> edges;
    for (int i = 0;i < newVertices.size();i++) {
        for (int j = i + 1;j < newVertices.size();j++) {
            edges.push_back({ lca.dist(newVertices[i],newVertices[j]),{i,j} });
        }
    }

    int ans = mst.findMST(edges, newVertices.size());
    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 'int MST::findMST(std::vector<std::pair<int, std::pair<int, int> > >&, int)':
roadsideadverts.cpp:56:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int i = 0;i < edges.size();i++) {
      |                        ~~^~~~~~~~~~~~~~
roadsideadverts.cpp: In member function 'void LCA::dfs(int, int, int)':
roadsideadverts.cpp:85: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]
   85 |   for (int i = 0; i < graph[v].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
roadsideadverts.cpp: In function 'int query(int, int, int, int, int)':
roadsideadverts.cpp:153:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |     for (int i = 0;i < nodes.size();i++) {
      |                    ~~^~~~~~~~~~~~~~
roadsideadverts.cpp:154:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |         for (int j = i;j < nodes.size();j++) {
      |                        ~~^~~~~~~~~~~~~~
roadsideadverts.cpp:163:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |     for (int i = 0;i < newVertices.size();i++) {
      |                    ~~^~~~~~~~~~~~~~~~~~~~
roadsideadverts.cpp:164:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |         for (int j = i + 1;j < newVertices.size();j++) {
      |                            ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 11600 KB Output is correct
2 Correct 52 ms 12852 KB Output is correct
3 Correct 53 ms 12624 KB Output is correct
4 Correct 48 ms 12704 KB Output is correct
5 Correct 47 ms 12812 KB Output is correct
6 Correct 48 ms 12888 KB Output is correct
7 Correct 66 ms 12636 KB Output is correct
8 Correct 47 ms 12892 KB Output is correct
9 Correct 49 ms 12888 KB Output is correct
10 Correct 47 ms 12892 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 10728 KB Output is correct
2 Correct 26 ms 12380 KB Output is correct
3 Correct 25 ms 12376 KB Output is correct
4 Correct 31 ms 12380 KB Output is correct
5 Correct 36 ms 12372 KB Output is correct
6 Correct 25 ms 12376 KB Output is correct
7 Correct 25 ms 12376 KB Output is correct
8 Correct 24 ms 12372 KB Output is correct
9 Correct 23 ms 12432 KB Output is correct
10 Correct 25 ms 12380 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 68 ms 11600 KB Output is correct
3 Correct 52 ms 12852 KB Output is correct
4 Correct 53 ms 12624 KB Output is correct
5 Correct 48 ms 12704 KB Output is correct
6 Correct 47 ms 12812 KB Output is correct
7 Correct 48 ms 12888 KB Output is correct
8 Correct 66 ms 12636 KB Output is correct
9 Correct 47 ms 12892 KB Output is correct
10 Correct 49 ms 12888 KB Output is correct
11 Correct 47 ms 12892 KB Output is correct
12 Correct 26 ms 10728 KB Output is correct
13 Correct 26 ms 12380 KB Output is correct
14 Correct 25 ms 12376 KB Output is correct
15 Correct 31 ms 12380 KB Output is correct
16 Correct 36 ms 12372 KB Output is correct
17 Correct 25 ms 12376 KB Output is correct
18 Correct 25 ms 12376 KB Output is correct
19 Correct 24 ms 12372 KB Output is correct
20 Correct 23 ms 12432 KB Output is correct
21 Correct 25 ms 12380 KB Output is correct
22 Correct 63 ms 11868 KB Output is correct
23 Correct 62 ms 11100 KB Output is correct
24 Correct 73 ms 12432 KB Output is correct
25 Correct 61 ms 12636 KB Output is correct
26 Correct 58 ms 12632 KB Output is correct
27 Correct 57 ms 12636 KB Output is correct
28 Correct 56 ms 12688 KB Output is correct
29 Correct 72 ms 12624 KB Output is correct
30 Correct 56 ms 12628 KB Output is correct
31 Correct 57 ms 12624 KB Output is correct