제출 #153915

#제출 시각아이디문제언어결과실행 시간메모리
153915andrewEvacuation plan (IZhO18_plan)C++17
100 / 100
2296 ms95928 KiB
#include <bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #pragma GCC optimize("-O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #define fi first #define se second #define p_b push_back #define pll pair<ll,ll> #define pii pair<int,int> #define m_p make_pair #define all(x) x.begin(),x.end() #define sset ordered_set #define sqr(x) (x)*(x) #define pw(x) (1ll << x) using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; const ll MAXN = 1123456; const ll N = 2e5; mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count()); template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template <typename T> void vout(T s){cout << s << endl;exit(0);} vector <pll> v[MAXN]; vector <ll> V[MAXN]; ll p[MAXN]; ll get(ll x){ if(p[x] != x)p[x] = get(p[x]); return p[x]; } int main(){ ios_base :: sync_with_stdio(0); cin.tie(0); ll n, m; cin >> n >> m; while(m--){ ll a, b, c; cin >> a >> b >> c; v[a].p_b({b, c}); v[b].p_b({a, c}); } set <pll> st; vector <ll> dp(n + 1), f(n + 1); for(int i = 1; i <= n; i++)dp[i] = 1e18; ll k; cin >> k; map <ll, vector <ll>> mp; while(k--){ ll x; cin >> x; dp[x] = 0; st.insert({0ll, x}); } while(!st.empty()){ pll xe = *st.begin(); st.erase(st.begin()); for(auto i : v[xe.se]){ ll val = xe.fi + i.se, to = i.fi; if(dp[to] > val){ st.erase({dp[to], to}); dp[to] = val; st.insert({dp[to], to}); } } } vector <ll> b; for(int i = 1; i <= n; i++){ mp[dp[i]].p_b(i); } for(auto i : mp)b.p_b(i.fi); ll N = b.size(); ll q; cin >> q; vector <pll> t(q); for(int i = 0; i < q; i++)cin >> t[i].fi >> t[i].se; vector <ll> l(q), r(q); for(int i = 0; i < q; i++)r[i] = N - 1; for(int step = 0; step < 19; step++){ for(int i = 1; i <= n; i++){ p[i] = i; f[i] = 0; } for(int i = 0; i < q; i++)if(l[i] < r[i]){ ll mid = (l[i] + r[i] + 1) >> 1; V[mid].p_b(i); } for(int i = N - 1; i >= 0; i--){ for(auto k : mp[b[i]]){ for(auto j : v[k])if(f[j.fi]){ if(get(k) != get(j.fi)){ p[get(j.fi)] = get(k); } } f[k] = 1; } for(auto k : V[i]){ if(get(t[k].fi) == get(t[k].se))l[k] = i; else r[k] = i - 1; } V[i].clear(); } } for(int i = 0; i < q; i++)cout << b[l[i]] << "\n"; return 0; }
#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...