Submission #79475

#	Time	Username	Problem	Language	Result	Execution time	Memory
79475		JustInCase	Evacuation plan (IZhO18_plan)	C++17	100 / 100	712 ms	73968 KiB

plan

#include <bits/stdc++.h>

const int32_t MAX_N = 1e5;
const int32_t LOG_MAX_N = 17;
const int32_t MAX_M = 5e5;
const int32_t INF = 2e9;

class Graph {
private:
	struct Node {
		bool isVisited;
		int32_t id, dist;
		std::vector< int32_t > v;
	
		Node() {
			dist = INF;
		}
	};

	struct Edge {
		int32_t w;
		Node *u, *v;

		Node* Get(Node *x) const {
			if(u == x) {
				return v;
			}
			else {
				return u;
			}
		}
	};

public:
	int32_t cntNodes, cntEdges;
	Node nodes[MAX_N + 5];
	Edge edges[MAX_M + 5];

	void Init(int32_t _cntNodes, int32_t _cntEdges) {
		cntNodes = _cntNodes;
		cntEdges = _cntEdges;
	
		for(int32_t i = 1; i <= _cntNodes; i++) {
			nodes[i].id = i;
		}
	}
		
	void AddEdge(Node *u, Node *v, int32_t w, int32_t ind) {
		u->v.push_back(ind);
		v->v.push_back(ind);

		edges[ind] = { w, u, v };
	}
	
	friend bool operator< (const std::pair< int32_t, Node* > &x, const std::pair< int32_t, Node* > &y) {
		return x.first > y.first;
	}

	void Dijkstra(const std::vector< int32_t > &st) {
		std::priority_queue< std::pair< int32_t, Node* > > pq;

		for(auto &x : st) {
			nodes[x].dist = 0;
			pq.push({ 0, &nodes[x] });
		}

		while(!pq.empty()) {
			Node *curr = pq.top().second;
			pq.pop();

			if(curr->isVisited) {
				continue;
			}
			curr->isVisited = true;

			for(auto &x : curr->v) {
				Node *nxtNode = edges[x].Get(curr);
				if(!nxtNode->isVisited && nxtNode->dist > curr->dist + edges[x].w) {
					nxtNode->dist = curr->dist + edges[x].w;
					pq.push({ nxtNode->dist, nxtNode });
				}
			}
		}
	}
};

struct Edge {
	int32_t u, v, minDist;

	bool operator< (const Edge &other) const {
		return minDist > other.minDist;
	}
};

Graph g;
Edge edges[MAX_M + 5];

class DSU {
private:
	int32_t parent[MAX_N + 5], siz[MAX_N + 5];

public:
	void Init(int32_t _cntNodes) {
		for(int32_t i = 1; i <= _cntNodes; i++) {
			parent[i] = i;
			siz[i] = 1;
		}
	}

	int32_t Find(int32_t x) {
		if(parent[x] == x) {
			return x;
		}
		else {
			parent[x] = Find(parent[x]);
			return parent[x];
		}
	}

	void Unite(int32_t x, int32_t y) {
		if(siz[x] > siz[y]) {
			parent[y] = x;
		}
		else if(siz[x] < siz[y]) {
			parent[x] = y;
		}
		else {
			parent[y] = x;
			siz[x] += siz[y];
		}
	}
};

DSU dsu;

class Tree {
private:
	struct Node {
		bool isVisited;
		int32_t id, inTime, outTime;
		std::pair< Node*, int32_t > ancs[LOG_MAX_N + 5];
		std::vector< std::pair< Node*, int32_t > > v;
	
		bool IsAncOf(Node *x) const {
			if(inTime <= x->inTime && outTime >= x->outTime) {
				return true;
			}
			
			return false;
		}
	};

public:
	int32_t cntNodes;
	Node nodes[MAX_N + 5];

	void Init(int32_t _cntNodes) {
		cntNodes = _cntNodes;

		for(int32_t i = 1; i <= _cntNodes; i++) {
			nodes[i].id = i;
			
			for(int32_t j = 0; j < LOG_MAX_N; j++) {
				nodes[i].ancs[j] = { nullptr, 0 };
			}
		}
	}

	void AddEdge(Node *u, Node *v, int32_t w) {
		u->v.push_back({ v, w });
		v->v.push_back({ u, w });
	}

	void PrecomputeDfs(Node *nd, int32_t &dfsTime) {
		nd->isVisited = true;
		nd->inTime = dfsTime++;

		for(auto &x : nd->v) {
			if(!x.first->isVisited) {
				PrecomputeDfs(x.first, dfsTime);
			}
			else {
				nd->ancs[0] = { x.first, x.second };
			}
		}

		nd->outTime = dfsTime - 1;
	}

	void PrecomputeAncs() {
		for(int32_t j = 1; j < LOG_MAX_N; j++) {
			for(int32_t i = 1; i <= cntNodes; i++) {
				if(nodes[i].ancs[j - 1].first != nullptr) {
					nodes[i].ancs[j] = { 
						nodes[i].ancs[j - 1].first->ancs[j - 1].first,
						std::min(nodes[i].ancs[j - 1].second, nodes[i].ancs[j - 1].first->ancs[j - 1].second)
					};
				}
			}
		}
	}

	int32_t GetMinDistBetween(Node *u, Node *v) {
		int32_t ans = INF;
		
		for(int32_t i = LOG_MAX_N - 1; i >= 0; i--) {
			if(u->ancs[i].first != nullptr && !u->ancs[i].first->IsAncOf(v)) {
				ans = std::min(ans, u->ancs[i].second);
				u = u->ancs[i].first;
			}
		}

		for(int32_t i = LOG_MAX_N - 1; i >= 0; i--) {
			if(v->ancs[i].first != nullptr && !v->ancs[i].first->IsAncOf(u)) {
				ans = std::min(ans, v->ancs[i].second);
				v = v->ancs[i].first;
			}
		}

		if(!u->IsAncOf(v)) {
			ans = std::min(ans, u->ancs[0].second);
		}
		if(!v->IsAncOf(u)) {
			ans = std::min(ans, v->ancs[0].second);
		}

		return ans;
	}
};

Tree t;

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

	int32_t n, m;
	std::cin >> n >> m;

	g.Init(n, m);

	for(int32_t i = 0; i < m; i++) {
		int32_t u, v, w;
		std::cin >> u >> v >> w;
		
		g.AddEdge(&g.nodes[u], &g.nodes[v], w, i);
	}

	int32_t k;
	std::cin >> k;

	std::vector< int32_t > special(k); 
	for(int32_t i = 0; i < k; i++) {
		std::cin >> special[i];
	}

	g.Dijkstra(special);

	for(int32_t i = 0; i < m; i++) {
		edges[i] = { g.edges[i].u->id, g.edges[i].v->id, std::min(g.edges[i].u->dist, g.edges[i].v->dist) };
	}

	std::sort(edges, edges + m);
	
	dsu.Init(n);
	t.Init(n);
	for(int32_t i = 0; i < m; i++) {
		int32_t parU = dsu.Find(edges[i].u);
		int32_t parV = dsu.Find(edges[i].v);

		if(parU != parV) {
			dsu.Unite(parU, parV);
			t.AddEdge(&t.nodes[edges[i].u], &t.nodes[edges[i].v], edges[i].minDist);
		}
	}

	int32_t dfsTime = 0;
	t.PrecomputeDfs(&t.nodes[1], dfsTime);

	t.PrecomputeAncs();

	int32_t q;
	std::cin >> q;

	for(int32_t i = 0; i < q; i++) {
		int32_t u, v;
		std::cin >> u >> v;

		std::cout << t.GetMinDistBetween(&t.nodes[u], &t.nodes[v]) << '\n';
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46