제출 #889466

#제출 시각아이디문제언어결과실행 시간메모리
889466DenkataEvacuation plan (IZhO18_plan)C++14
19 / 100
420 ms68148 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; const int maxn = 1e5+3; long long i,j,p,q,n,m,k,raz[maxn],Q; struct Put { long long v,d; }; bool operator<(Put a,Put b) { return a.d>b.d; } priority_queue <Put> pq; vector <Put> v[maxn]; map <int,bool> povtorki; long long par[maxn],sz[maxn]; vector <long long> stoinosti; vector <pair<long long,long long>> group[maxn]; long long tek; struct roll_back { long long a,para; long long b,parb; long long szb; long long where; }; stack <roll_back> s; struct Zaqvka { long long l,r,id; }; vector <Zaqvka> queries; long long ans[maxn]; void roll_back(long long pos) { while(!s.empty() && s.top().where<=pos) { auto t = s.top(); s.pop(); par[t.a] = t.para; par[t.b] = t.parb; sz[t.para]-=t.szb; } } long long Find(long long p) { if(par[p]==p) return p; return Find(par[p]); } void Union(long long p,long long q,long long where) { // cout<<"Union "<<p<<" "<<q<<" "<<where<<endl; long long parp,parq; parp = Find(p); parq = Find(q); if(parp==parq)return ; //cout<<"svurzvame "<<p<<" "<<q<<endl; if(sz[parp]<sz[parq])swap(parp,parq),swap(p,q); s.push({p,parp,q,parq,sz[parq],where}); par[parq] = parp; sz[parp]+=sz[parq]; } void solve(long long l,long long r,vector <long long> &active) { if(r<l)return ; if(active.empty())return ; if(l==r) { for(auto j:active) ans[queries[j].id] = stoinosti[l-1]; return ; } long long mid = (l+r)/2; ///jumping through values if(tek>mid) { for(i=tek-1;i>=mid;i--) { for(auto j:group[i]) { Union(j.first,j.second,i); } } } else if(tek<mid) roll_back(mid-1); //cout<<"tuk"<<endl; tek = mid; vector <long long> left; vector <long long> right; for(auto i:active) { // cout<<i<<" is active"<<endl; p = queries[i].l; q = queries[i].r; // cout<<p<<" pq "<<q<<endl; if(Find(p)==Find(q)) right.push_back(i); else left.push_back(i); } active.clear(); /** cout<<"left "<<endl; for(auto i:left) cout<<i<<endl; cout<<"right"<<endl; for(auto i:right) cout<<i<<endl; */ solve(l,mid,left); solve(mid+1,r,right); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>m; for(i=1;i<=m;i++) { cin>>p>>q>>j; v[p].push_back({q,j}); v[q].push_back({p,j}); } for(i=1;i<=n;i++) par[i] = i,sz[i] = 1; long long cool; cin>>cool; while(cool--) { cin>>p; pq.push({p,0}); } for(i=1;i<=n;i++) raz[i] = -1; long long cnt; while(!pq.empty()) { auto t = pq.top(); pq.pop(); if(raz[t.v]==-1) { raz[t.v] = t.d; if(!povtorki[raz[t.v]]) stoinosti.push_back(raz[t.v]),povtorki[raz[t.v]] = true; //group[nomer[raz[t.v]]].push_back(t.v); for(auto i:v[t.v]) { if(raz[i.v]==-1) pq.push({i.v,t.d+i.d}); } } } sort(stoinosti.begin(),stoinosti.end()); for(i=1;i<=n;i++) { p = lower_bound(stoinosti.begin(),stoinosti.end(),raz[i])-stoinosti.begin(); // cout<<i<<" grupa "<<p<<" "<<stoinosti[p]<<endl; for(auto j:v[i]) { long long h = min(raz[i],raz[j.v]); p = lower_bound(stoinosti.begin(),stoinosti.end(),h)-stoinosti.begin(); // cout<<i<<" "<<j.v<<" "<<h<<endl; group[p].push_back({i,j.v}); } } /** for(i=1;i<=n;i++) cout<<r[i]<<" "; */ tek = stoinosti.size(); cin>>Q; for(i=1;i<=Q;i++) { cin>>p>>q; queries.push_back({p,q,i-1}); } vector <long long> nach; for(i=0;i<Q;i++) nach.push_back(i); solve(0,stoinosti.size()-1,nach); for(i=0;i<Q;i++) cout<<ans[i]<<endl; cout<<endl; 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 'int main()':
plan.cpp:140:15: warning: unused variable 'cnt' [-Wunused-variable]
  140 |     long long cnt;
      |               ^~~
#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...