Submission #1217670

#TimeUsernameProblemLanguageResultExecution timeMemory
1217670M_SH_OEvacuation plan (IZhO18_plan)C++20
100 / 100
1008 ms41884 KiB
#include <bits/stdc++.h> //#include "grader.h" /*#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp>*/ #define ll long long #define ll1 long long #define ull unsigned long long #define dou long double #define str string #define vll vector<ll> #define vi vector<int> #define pll pair<ll, ll> #define vpll vector<pll> #define vbool vector<bool> #define vstr vector<str> #define vvll vector<vll> #define pb push_back #define pf push_front //#define endl "\n" #define fr first #define se second // #define sortcmp(a) sort(a.begin(), a.end(), cmp) #define sort(a) sort(a.begin(), a.end()) #define all(a) a.begin(), a.end() #define reverse(a) reverse(a.begin(), a.end()) #define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define INF 1000000000000000000 #define ordered_set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update> using namespace std; //using namespace __gnu_pbds; mt19937 rng(1488); ll randll(ll l, ll r){ return uniform_int_distribution<ll>(l, r)(rng); } vvll s1; vll p; ll find(ll v) { if (p[v] == v) return v; return p[v] = find(p[v]); } vll unite(ll a, ll b) { a = find(a); b = find(b); if (a == b) return {}; if (s1[a].size() < s1[b].size()) { p[a] = b; for (auto i : s1[a]) { s1[b].pb(i); } return s1[a]; } else { p[b] = a; for (auto i : s1[b]) { s1[a].pb(i); } return s1[b]; } }/* vll tree1, d; void push(ll v, ll tl, ll tr) { if (tl == tr) return; tree1[v*2] += d[v]; tree1[v*2+1] += d[v]; d[v*2] += d[v]; d[v*2+1] += d[v]; d[v] = 0; tree1[v] = tree1[v*2]+tree1[v*2+1]; } void bt(ll v, ll tl, ll tr, vll& a) { if (tl == tr) { tree1[v] = a[tl]; return; } ll tm = (tl+tr)/2; bt(v*2, tl, tm, a); bt(v*2, tm+1, tr, a); tree1[v] = tree1[v*2]+tree1[v*2+1]; } ll get(ll l, ll r, ll v, ll tl, ll tr) { if (l <= tl && tr <= r) return tree1[v]; if (tl > r || tr < l) return 0; ll tm = (tl+tr)/2; push(v, tl, tr); return get(l, r, v*2, tl, tm)+get(l, r, v*2+1, tm+1, tr); } void update(ll l, ll r, ll val, ll v, ll tl, ll tr) { if (l <= tl && tr <= r) { tree1[v] += val; d[v] += val; push(v, tl, tr); return; } if (tl > r || tr < l) return; ll tm = (tl+tr)/2; push(v, tl, tr); update(l, r, val, v*2, tl, tm); update(l, r, val, v*2+1, tm+1, tr); tree1[v] = tree1[v*2]+tree1[v*2+1]; }*/ vector<vpll> g; int main(){ ll n, m; cin >> n >> m; g.resize(n+7); for (int i = 0; i < m; i ++) { ll a, b, c; cin >> a >> b >> c; g[a].pb({b, c}); g[b].pb({a, c}); } ll k; cin >> k; vll a(k); vll d(n+7, INF); for (int i = 0; i < k; i ++) { cin >> a[i]; d[a[i]] = 0; } set<pll> s; p.resize(n+7); s1.resize(n+7); for (int i = 1; i <= n; i ++) { p[i] = i; s.insert({d[i], i}); } while (!s.empty()) { pll p = *s.begin(); s.erase(s.begin()); for (auto i : g[p.se]) { if (p.fr+i.se < d[i.fr]) { s.erase({d[i.fr], i.fr}); d[i.fr] = p.fr+i.se; s.insert({d[i.fr], i.fr}); } } } vpll v; for (int i = 1; i <= n; i ++) { v.pb({d[i], i}); } sort(v); reverse(v); ll q; cin >> q; vpll qu(q); for (int i = 0; i < q; i ++) { cin >> qu[i].fr >> qu[i].se; s1[qu[i].fr].pb(i); s1[qu[i].se].pb(i); } vll res(q, -1); for (auto i : v) { for (auto j : g[i.se]) { if (d[j.fr] >= i.fr) { vll v1 = unite(j.fr, i.se); for (int i1 : v1) { if (res[i1] != -1) continue; if (find(qu[i1].fr) == find(qu[i1].se)) res[i1] = i.fr; } } } } for (int i = 0; i < q;i ++) { cout << res[i] << endl; } }
#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...