제출 #893986

#제출 시각아이디문제언어결과실행 시간메모리
893986borisAngelovEvacuation plan (IZhO18_plan)C++17
41 / 100
4029 ms34280 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]; vector<long long> toTry; struct Query { int from; int to; int idx; Query() { } Query(int _from, int _to, int _idx) { from = _from; to = _to; idx = _idx; } }; struct DSU { struct Roll { int *pos; int val; int t; }; int par[maxn]; int dep[maxn]; stack<Roll> rollback; void init() { while (!rollback.empty()) { rollback.pop(); } for (int i = 1; i <= n; ++i) { par[i] = i; dep[i] = 1; } } int root(int node) { if (node == par[node]) { return node; } return root(par[node]); } void connect(int x, int y, int tim) { x = root(x); y = root(y); if (x == y) { return; } if (dep[x] < dep[y]) { swap(x, y); } rollback.push({&par[y], par[y], tim}); par[y] = x; if (dep[x] == dep[y]) { rollback.push({&dep[x], dep[x], tim}); ++dep[x]; } } void rollbackSmaller(int tim) { while (!rollback.empty() && tim >= rollback.top().t) { *rollback.top().pos = rollback.top().val; rollback.pop(); } } inline bool areConnected(int x, int y) { return root(x) == root(y); } }; DSU dsu; vector<Query> queries; long long answers[maxn]; vector<pair<int, int>> byValue[maxn]; void parallelBinarySearch(int l, int r, vector<int>& curr) { if (l > r) { return; } if (curr.empty()) { return; } if (l == r) { for (int i = 0; i < curr.size(); ++i) { answers[queries[curr[i]].idx] = toTry[l]; } return; } int mid = (l + r) / 2; for (int i = toTry.size() - 1; i >= mid + 1; --i) { for (int j = 0; j < byValue[i].size(); ++j) { dsu.connect(byValue[i][j].first, byValue[i][j].second, i); } } dsu.rollbackSmaller(mid); vector<int> toLeft; vector<int> toRight; for (int i = 0; i < curr.size(); ++i) { if (dsu.areConnected(queries[curr[i]].from, queries[curr[i]].to) == true) { toRight.push_back(curr[i]); } else { toLeft.push_back(curr[i]); } } parallelBinarySearch(l, mid, toLeft); parallelBinarySearch(mid + 1, r, toRight); } vector<long long> uniqueDistances() { set<long long> s; vector<long long> res; for (int i = 1; i <= n; ++i) { 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)); } } } toTry = uniqueDistances(); for (int i = 1; i <= n; ++i) { for (int j = 0; j < g[i].size(); ++j) { if (i < g[i][j].first) { long long d = min(dist[i], dist[g[i][j].first]); int l = 0; int r = toTry.size() - 1; while (l <= r) { int mid = (l + r) / 2; if (toTry[mid] >= d) { r = mid - 1; } else { l = mid + 1; } } byValue[l].push_back(make_pair(i, g[i][j].first)); } } } cin >> q; for (int i = 1; i <= q; ++i) { int from, to; cin >> from >> to; queries.push_back(Query(from, to, i - 1)); } dsu.init(); vector<int> starting; for (int i = 0; i < q; ++i) { starting.push_back(i); } parallelBinarySearch(0, toTry.size() - 1, starting); for (int i = 0; i < q; ++i) { cout << answers[i] << "\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 */

컴파일 시 표준 에러 (stderr) 메시지

plan.cpp: In function 'void parallelBinarySearch(int, int, std::vector<int>&)':
plan.cpp:136:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |         for (int i = 0; i < curr.size(); ++i)
      |                         ~~^~~~~~~~~~~~~
plan.cpp:148: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]
  148 |         for (int j = 0; j < byValue[i].size(); ++j)
      |                         ~~^~~~~~~~~~~~~~~~~~~
plan.cpp:159:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |     for (int i = 0; i < curr.size(); ++i)
      |                     ~~^~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:241: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]
  241 |         for (int i = 0; i < g[node].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~
plan.cpp:258: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]
  258 |         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...