oj.uz

Submission #79475

# Submission time Handle Problem Language Result Execution time Memory
79475 2018-10-14T08:38:43 Z JustInCase Evacuation plan (IZhO18_plan) C++17
100 / 100
 712 ms 73968 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 42616 KB Output is correct
2 Correct 39 ms 42872 KB Output is correct
3 Correct 39 ms 42744 KB Output is correct
4 Correct 39 ms 42616 KB Output is correct
5 Correct 39 ms 42744 KB Output is correct
6 Correct 39 ms 42744 KB Output is correct
7 Correct 38 ms 42620 KB Output is correct
8 Correct 38 ms 42616 KB Output is correct
9 Correct 38 ms 42872 KB Output is correct
10 Correct 39 ms 42792 KB Output is correct
11 Correct 39 ms 42872 KB Output is correct
12 Correct 39 ms 42872 KB Output is correct
13 Correct 42 ms 42804 KB Output is correct
14 Correct 39 ms 42756 KB Output is correct
15 Correct 39 ms 42740 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 42616 KB Output is correct
2 Correct 39 ms 42872 KB Output is correct
3 Correct 39 ms 42744 KB Output is correct
4 Correct 39 ms 42616 KB Output is correct
5 Correct 39 ms 42744 KB Output is correct
6 Correct 39 ms 42744 KB Output is correct
7 Correct 38 ms 42620 KB Output is correct
8 Correct 38 ms 42616 KB Output is correct
9 Correct 38 ms 42872 KB Output is correct
10 Correct 39 ms 42792 KB Output is correct
11 Correct 39 ms 42872 KB Output is correct
12 Correct 39 ms 42872 KB Output is correct
13 Correct 42 ms 42804 KB Output is correct
14 Correct 39 ms 42756 KB Output is correct
15 Correct 39 ms 42740 KB Output is correct
16 Correct 269 ms 53884 KB Output is correct
17 Correct 659 ms 73968 KB Output is correct
18 Correct 77 ms 45492 KB Output is correct
19 Correct 232 ms 55624 KB Output is correct
20 Correct 665 ms 73936 KB Output is correct
21 Correct 403 ms 59900 KB Output is correct
22 Correct 297 ms 59296 KB Output is correct
23 Correct 677 ms 73796 KB Output is correct
24 Correct 670 ms 73816 KB Output is correct
25 Correct 700 ms 73900 KB Output is correct
26 Correct 245 ms 55476 KB Output is correct
27 Correct 242 ms 55512 KB Output is correct
28 Correct 229 ms 55372 KB Output is correct
29 Correct 235 ms 55528 KB Output is correct
30 Correct 252 ms 55584 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 42616 KB Output is correct
2 Correct 38 ms 42596 KB Output is correct
3 Correct 38 ms 42616 KB Output is correct
4 Correct 39 ms 42616 KB Output is correct
5 Correct 37 ms 42616 KB Output is correct
6 Correct 38 ms 42620 KB Output is correct
7 Correct 38 ms 42628 KB Output is correct
8 Correct 38 ms 42572 KB Output is correct
9 Correct 39 ms 42616 KB Output is correct
10 Correct 38 ms 42616 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 59516 KB Output is correct
2 Correct 652 ms 73412 KB Output is correct
3 Correct 624 ms 73464 KB Output is correct
4 Correct 203 ms 57128 KB Output is correct
5 Correct 623 ms 73432 KB Output is correct
6 Correct 623 ms 73560 KB Output is correct
7 Correct 617 ms 73448 KB Output is correct
8 Correct 637 ms 73448 KB Output is correct
9 Correct 609 ms 73416 KB Output is correct
10 Correct 595 ms 73324 KB Output is correct
11 Correct 614 ms 73540 KB Output is correct
12 Correct 635 ms 73504 KB Output is correct
13 Correct 614 ms 73488 KB Output is correct
14 Correct 599 ms 73516 KB Output is correct
15 Correct 621 ms 73472 KB Output is correct
16 Correct 622 ms 73336 KB Output is correct
17 Correct 599 ms 73556 KB Output is correct
18 Correct 631 ms 73424 KB Output is correct
19 Correct 204 ms 58216 KB Output is correct
20 Correct 622 ms 73392 KB Output is correct
21 Correct 596 ms 73660 KB Output is correct
22 Correct 195 ms 55108 KB Output is correct
23 Correct 208 ms 55716 KB Output is correct
24 Correct 202 ms 55220 KB Output is correct
25 Correct 191 ms 55148 KB Output is correct
26 Correct 217 ms 55648 KB Output is correct
27 Correct 212 ms 58048 KB Output is correct
28 Correct 182 ms 55288 KB Output is correct
29 Correct 207 ms 57464 KB Output is correct
30 Correct 185 ms 55108 KB Output is correct
31 Correct 207 ms 57592 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 42616 KB Output is correct
2 Correct 39 ms 42872 KB Output is correct
3 Correct 39 ms 42744 KB Output is correct
4 Correct 39 ms 42616 KB Output is correct
5 Correct 39 ms 42744 KB Output is correct
6 Correct 39 ms 42744 KB Output is correct
7 Correct 38 ms 42620 KB Output is correct
8 Correct 38 ms 42616 KB Output is correct
9 Correct 38 ms 42872 KB Output is correct
10 Correct 39 ms 42792 KB Output is correct
11 Correct 39 ms 42872 KB Output is correct
12 Correct 39 ms 42872 KB Output is correct
13 Correct 42 ms 42804 KB Output is correct
14 Correct 39 ms 42756 KB Output is correct
15 Correct 39 ms 42740 KB Output is correct
16 Correct 269 ms 53884 KB Output is correct
17 Correct 659 ms 73968 KB Output is correct
18 Correct 77 ms 45492 KB Output is correct
19 Correct 232 ms 55624 KB Output is correct
20 Correct 665 ms 73936 KB Output is correct
21 Correct 403 ms 59900 KB Output is correct
22 Correct 297 ms 59296 KB Output is correct
23 Correct 677 ms 73796 KB Output is correct
24 Correct 670 ms 73816 KB Output is correct
25 Correct 700 ms 73900 KB Output is correct
26 Correct 245 ms 55476 KB Output is correct
27 Correct 242 ms 55512 KB Output is correct
28 Correct 229 ms 55372 KB Output is correct
29 Correct 235 ms 55528 KB Output is correct
30 Correct 252 ms 55584 KB Output is correct
31 Correct 39 ms 42616 KB Output is correct
32 Correct 38 ms 42596 KB Output is correct
33 Correct 38 ms 42616 KB Output is correct
34 Correct 39 ms 42616 KB Output is correct
35 Correct 37 ms 42616 KB Output is correct
36 Correct 38 ms 42620 KB Output is correct
37 Correct 38 ms 42628 KB Output is correct
38 Correct 38 ms 42572 KB Output is correct
39 Correct 39 ms 42616 KB Output is correct
40 Correct 38 ms 42616 KB Output is correct
41 Correct 336 ms 59516 KB Output is correct
42 Correct 652 ms 73412 KB Output is correct
43 Correct 624 ms 73464 KB Output is correct
44 Correct 203 ms 57128 KB Output is correct
45 Correct 623 ms 73432 KB Output is correct
46 Correct 623 ms 73560 KB Output is correct
47 Correct 617 ms 73448 KB Output is correct
48 Correct 637 ms 73448 KB Output is correct
49 Correct 609 ms 73416 KB Output is correct
50 Correct 595 ms 73324 KB Output is correct
51 Correct 614 ms 73540 KB Output is correct
52 Correct 635 ms 73504 KB Output is correct
53 Correct 614 ms 73488 KB Output is correct
54 Correct 599 ms 73516 KB Output is correct
55 Correct 621 ms 73472 KB Output is correct
56 Correct 622 ms 73336 KB Output is correct
57 Correct 599 ms 73556 KB Output is correct
58 Correct 631 ms 73424 KB Output is correct
59 Correct 204 ms 58216 KB Output is correct
60 Correct 622 ms 73392 KB Output is correct
61 Correct 596 ms 73660 KB Output is correct
62 Correct 195 ms 55108 KB Output is correct
63 Correct 208 ms 55716 KB Output is correct
64 Correct 202 ms 55220 KB Output is correct
65 Correct 191 ms 55148 KB Output is correct
66 Correct 217 ms 55648 KB Output is correct
67 Correct 212 ms 58048 KB Output is correct
68 Correct 182 ms 55288 KB Output is correct
69 Correct 207 ms 57464 KB Output is correct
70 Correct 185 ms 55108 KB Output is correct
71 Correct 207 ms 57592 KB Output is correct
72 Correct 402 ms 59948 KB Output is correct
73 Correct 677 ms 73800 KB Output is correct
74 Correct 671 ms 73920 KB Output is correct
75 Correct 666 ms 73948 KB Output is correct
76 Correct 663 ms 73924 KB Output is correct
77 Correct 675 ms 73860 KB Output is correct
78 Correct 669 ms 73804 KB Output is correct
79 Correct 677 ms 73880 KB Output is correct
80 Correct 685 ms 73792 KB Output is correct
81 Correct 701 ms 73844 KB Output is correct
82 Correct 681 ms 73884 KB Output is correct
83 Correct 670 ms 73784 KB Output is correct
84 Correct 676 ms 73860 KB Output is correct
85 Correct 670 ms 73740 KB Output is correct
86 Correct 699 ms 73788 KB Output is correct
87 Correct 712 ms 73960 KB Output is correct
88 Correct 697 ms 73900 KB Output is correct
89 Correct 394 ms 58388 KB Output is correct
90 Correct 703 ms 73804 KB Output is correct
91 Correct 638 ms 73944 KB Output is correct
92 Correct 236 ms 55496 KB Output is correct
93 Correct 307 ms 56392 KB Output is correct
94 Correct 238 ms 55484 KB Output is correct
95 Correct 234 ms 55468 KB Output is correct
96 Correct 316 ms 56196 KB Output is correct
97 Correct 369 ms 57692 KB Output is correct
98 Correct 244 ms 55380 KB Output is correct
99 Correct 380 ms 58544 KB Output is correct
100 Correct 230 ms 55488 KB Output is correct