Submission #1100149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100149		CpDark	Roadside Advertisements (NOI17_roadsideadverts)	C++17	100 / 100	73 ms	12892 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;

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 (stderr)

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 / 7
• Subtask 2: 23 / 23
• Subtask 3: 40 / 40
• Subtask 4: 30 / 30