Submission #893896

#TimeUsernameProblemLanguageResultExecution timeMemory
893896borisAngelovEvacuation plan (IZhO18_plan)C++17
41 / 100
4064 ms30760 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 100005; const long long inf = (1LL << 61); int n, m, k, q; int startCities[maxn]; vector<pair<int, int>> g[maxn]; long long dist[maxn]; struct DSU { int par[maxn]; int dep[maxn]; void init() { for (int i = 1; i <= n; ++i) { par[i] = i; dep[i] = 1; } } int root(int node) { if (node == par[node]) { return node; } return par[node] = root(par[node]); } void connect(int x, int y) { x = root(x); y = root(y); if (x == y) { return; } if (dep[x] >= dep[y]) { par[y] = x; if (dep[x] == dep[y]) { ++dep[x]; } } else { par[x] = y; } } bool areConnected(int x, int y) { return root(x) == root(y); } }; DSU dsu; vector<long long> toTry; struct Edge { int from; int to; long long w; Edge() { } Edge(int _from, int _to, long long _w) { from = _from; to = _to; w = _w; } bool operator < (const Edge& other) const { return w < other.w; } }; vector<Edge> edges; bool check(int from, int to, long long minW) { //cout << "checking for " << minW << endl; dsu.init(); int l = 0; int r = m - 1; while (l <= r) { int mid = (l + r) / 2; if (edges[mid].w >= minW) { r = mid - 1; } else { l = mid + 1; } } for (int i = l; i < m; ++i) { //cout << "add edge " << edges[i].from << ' ' << edges[i].to << ' ' << edges[i].w << endl; dsu.connect(edges[i].from, edges[i].to); } return dsu.areConnected(from, to); } long long solve(int from, int to) { //cout << "query " << from << " " << to << endl; int l = 0; int r = toTry.size() - 1; while (l <= r) { int mid = (l + r) / 2; if (check(from, to, toTry[mid]) == true) { l = mid + 1; } else { r = mid - 1; } } return toTry[r]; } vector<long long> uniqueDistances() { set<long long> s; vector<long long> res; for (int i = 1; i <= n; ++i) { if (s.find(dist[i]) == s.end()) { s.insert(dist[i]); } } for (auto element : s) { res.push_back(element); } return res; } void fastIO() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } int main() { fastIO(); cin >> n >> m; for (int i = 1; i <= m; ++i) { int x, y, w; cin >> x >> y >> w; g[x].push_back(make_pair(y, w)); g[y].push_back(make_pair(x, w)); } cin >> k; for (int i = 1; i <= k; ++i) { cin >> startCities[i]; } for (int i = 1; i <= n; ++i) { dist[i] = inf; } priority_queue<pair<long long, int>> pq; for (int i = 1; i <= k; ++i) { pq.push(make_pair(0, startCities[i])); dist[startCities[i]] = 0; } while (!pq.empty()) { int node = pq.top().second; long long curr = -pq.top().first; pq.pop(); for (int i = 0; i < g[node].size(); ++i) { long long path = g[node][i].second + curr; int to = g[node][i].first; if (dist[to] > path) { dist[to] = path; pq.push(make_pair(-path, to)); } } } /*cout << "check " << endl; for (int i = 1; i <= n; ++i) { cout << dist[i] << ' '; } cout << endl;*/ toTry = uniqueDistances(); for (int i = 1; i <= n; ++i) { for (int j = 0; j < g[i].size(); ++j) { if (i < g[i][j].first) { edges.push_back(Edge(i, g[i][j].first, min(dist[i], dist[g[i][j].first]))); } } } sort(edges.begin(), edges.end()); cin >> q; for (int i = 1; i <= q; ++i) { int from, to; cin >> from >> to; cout << solve(from, to) << "\n"; } return 0; } /* 9 12 1 9 4 1 2 5 2 3 7 2 4 3 4 3 6 3 6 4 8 7 10 6 7 5 5 8 1 9 5 7 5 4 12 6 8 2 2 4 7 5 1 6 5 3 4 8 5 8 1 5 */

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:225:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  225 |         for (int i = 0; i < g[node].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~
plan.cpp:251:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  251 |         for (int j = 0; j < g[i].size(); ++j)
      |                         ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...