제출 #893833

#제출 시각아이디문제언어결과실행 시간메모리
893833kigashEvacuation plan (IZhO18_plan)C++17
100 / 100
666 ms79932 KiB
#include "bits/stdc++.h" using namespace std; // #pragma comment(linker, "/stack:200000000") // #pragma GCC optimize("Ofast") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") using ll = long long; using ld = long double; #define pb push_back #define ff first #define ss second #define sz(x) (ll)(x).size() #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() void freopen(string s) { freopen((s+".in").c_str(), "r", stdin); freopen((s+".out").c_str(), "w", stdout); } void IOIGold2024_InshAllah() { ios_base::sync_with_stdio(false); cin.tie(NULL); } ll binmul(ll a, ll b, ll c) { ll res = 0; while(b) { if(b&1) (res += a) %= c; (a += a) %= c; b >>= 1; } return res; } ll binpow(ll a, ll b, ll c) { ll res = 1; while(b) { if(b&1) (res *= a) %= c; (a *= a) %= c; b >>= 1; } return res; } template<typename T> T gcd(T a, T b) { if(b==0) return a; return gcd(b, a%b); } template<typename T> T lcm(T a, T b) { return a/gcd(a, b)*b; } mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ld rnd() { return rng()%INT_MAX*1.0/INT_MAX; } const ll inf = 1e18+7, MX = LLONG_MAX, MN = LLONG_MIN; const ll mod = 1e9+7, N = 5e5+5; struct que { ll u, v; } c[N]; vector<pair<ll, ll>> g[N], t; vector<pair<ll*, ll>> upd; ll d[N], ans[N], u[N], v[N], w[N], p[N], sz[N]; ll get(ll x) { while(p[x]!=-1) x = p[x]; return x; } void update(ll x, ll y) { x = get(x), y = get(y); if(x==y) return; if(sz[x]>sz[y]) { upd.emplace_back(&p[y], p[y]); p[y] = x; } else if(sz[x]<sz[y]) { upd.emplace_back(&p[x], p[x]); p[x] = y; } else { upd.emplace_back(&p[x], p[x]); upd.emplace_back(&sz[y], sz[y]); p[x] = y, sz[y]++; } } void solve(ll l, ll r, vector<ll> a) { if(l==r-1 || a.empty()) { for(auto x: a) ans[x] = t[l].ff; return; } ll mid = l+(r-l)/2, st = sz(upd); for(ll i=l; i<mid; i++) { update(u[t[i].ss], v[t[i].ss]); } vector<ll> lt, rt; for(auto x: a) { // cout<<l<<" "<<r<<" - "<<x<<"\n"; if(get(c[x].u)==get(c[x].v)) lt.pb(x); else rt.pb(x); } solve(mid, r, rt); while(sz(upd)>st) { *upd.back().ff = upd.back().ss; upd.pop_back(); } solve(l, mid, lt); } void kigash() { ll n, m, k, q; cin>>n>>m; for(ll i=1; i<=m; i++) { cin>>u[i]>>v[i]>>w[i]; g[u[i]].pb({v[i], w[i]}), g[v[i]].pb({u[i], w[i]}); } cin>>k; set<pair<ll, ll>> st; for(ll i=1; i<=n; i++) d[i] = inf, p[i] = -1; while(k--) { ll v; cin>>v; st.insert({0, v}), d[v] = 0; } while(!st.empty()) { ll v = (*st.begin()).ss; st.erase(st.begin()); for(auto [to, w]: g[v]) { if(d[to]>d[v]+w) { st.erase({d[to], to}); d[to] = d[v]+w; st.insert({d[to], to}); } } } for(ll i=1; i<=m; i++) { t.pb({min(d[u[i]], d[v[i]]), i}); } sort(rall(t)); // for(auto [x, y]: t) cout<<x<<" "; cin>>q; vector<ll> tmp; for(ll i=1; i<=q; i++) { tmp.pb(i); cin>>c[i].u>>c[i].v; } solve(0, sz(t), tmp); for(ll i=1; i<=q; i++) cout<<ans[i]<<"\n"; return; } signed main(/*Kigash Amir*/) { // freopen(""); IOIGold2024_InshAllah(); ll tt = 1; // cin>>tt; for(ll i=1; i<=tt; i++) { kigash(); } }

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

plan.cpp: In function 'void freopen(std::string)':
plan.cpp:17:33: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 | void freopen(string s) { freopen((s+".in").c_str(), "r", stdin); freopen((s+".out").c_str(), "w", stdout); }
      |                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:17:73: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 | void freopen(string s) { freopen((s+".in").c_str(), "r", stdin); freopen((s+".out").c_str(), "w", stdout); }
      |                                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...