Submission #466605

#TimeUsernameProblemLanguageResultExecution timeMemory
466605TeaTimeEvacuation plan (IZhO18_plan)C++17
0 / 100
760 ms26380 KiB
//#pragma GCC optimize("O3") //#pragma GCC target("avx2") #include <iostream> #include <vector> #include <string> #include <algorithm> #include <map> #include <set> #include <queue> #include <unordered_map> #include <cmath> using namespace std; #define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); typedef long long ll; typedef long double ld; const ll SZ = 1e5 + 100, LG = 20, INF = 1e9 * 1e9 + 100; ll n, m, dsu[SZ]; ll k; vector<ll> bad; vector<vector<pair<ll, ll>>> gr; struct qs { int u, v, i, l, r; }; vector<qs> queries; vector<qs> st[SZ]; ll dist[SZ]; vector<pair<ll, ll>> srt; void djikstra() { set<pair<ll, ll>> st; for (int i = 0; i < n; i++) dist[i] = INF; for (auto c : bad) dist[c] = 0; for (int i = 0; i < n; i++) st.insert({ dist[i], i }); while (!st.empty()) { pair<ll, ll> v = (*st.begin()); st.erase(st.begin()); for (auto to : gr[v.second]) { if (dist[to.first] > v.first + to.second) { st.erase({ dist[to.first], to.first }); dist[to.first] = v.first + to.second; st.insert({ dist[to.first], to.first }); } } } for (int i = 0; i < n; i++) srt.push_back({ dist[i], i }); sort(srt.rbegin(), srt.rend()); } ll par(int v) { if (dsu[v] == v) return v; else return dsu[v] = par(dsu[v]); } void uni(int v, int u) { v = par(v); u = par(u); if (v != u) { dsu[v] = u; } } void add(int v) { for (auto to : gr[v]) { if (dist[to.first] >= dist[v]) uni(to.first, v); } } signed main() { fastInp; cin >> n >> m; gr.resize(n); for (int i = 0; i < m; i++) { ll u, v, c; cin >> u >> v >> c; u--; v--; gr[u].push_back({ v, c }); gr[v].push_back({ u, c }); } cin >> k; bad.resize(k); for (auto& c : bad) cin >> c; djikstra(); ll q; cin >> q; int md = (n - 1) / 2; for (int i = 0; i < q; i++) { ll u, v; cin >> u >> v; u--; v--; queries.push_back({ u, v, i, -1, n }); st[md].push_back({ u, v, i, -1, n }); } vector<ll> ans(q); for (int j = 0; j < LG; j++) { for (int i = 0; i < n; i++) dsu[i] = i; for (int i = 0; i <= n; i++) { if (i >= 1) { add(i - 1); } while (!st[i].empty()) { qs cur = st[i].back(); st[i].pop_back(); if (par(cur.u) == par(cur.v)) { cur.r = i; } else { cur.l = i; } if (cur.l == cur.r - 1) { ans[cur.i] = dist[cur.l]; continue; } int md2 = (cur.r + cur.l) / 2; st[md2].push_back(cur); } } } for (auto c : ans) cout << c << "\n"; return 0; }

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:105:29: warning: narrowing conversion of 'u' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  105 |         queries.push_back({ u, v, i, -1, n });
      |                             ^
plan.cpp:105:32: warning: narrowing conversion of 'v' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  105 |         queries.push_back({ u, v, i, -1, n });
      |                                ^
plan.cpp:105:42: warning: narrowing conversion of 'n' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  105 |         queries.push_back({ u, v, i, -1, n });
      |                                          ^
plan.cpp:106:28: warning: narrowing conversion of 'u' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  106 |         st[md].push_back({ u, v, i, -1, n });
      |                            ^
plan.cpp:106:31: warning: narrowing conversion of 'v' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  106 |         st[md].push_back({ u, v, i, -1, n });
      |                               ^
plan.cpp:106:41: warning: narrowing conversion of 'n' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  106 |         st[md].push_back({ u, v, i, -1, n });
      |                                         ^
#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...