제출 #890711

#제출 시각아이디문제언어결과실행 시간메모리
890711DenkataEvacuation plan (IZhO18_plan)C++14
100 / 100
441 ms82532 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 <long long,bool> povtorki; long long par[maxn],rnk[maxn]; vector <long long> stoinosti; vector <pair<long long,long long>> group[maxn]; long long tek; struct roll_back { long long a; long long b; long long rnka,rnkb; 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(); rnk[t.a] = t.rnka; rnk[t.b] = t.rnkb; par[t.a] = t.a; par[t.b] = t.b; } } 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; p = Find(p); q = Find(q); if(p==q)return ; //cout<<"svurzvame "<<p<<" "<<q<<endl; s.push({p,q,rnk[p],rnk[q],where}); if(rnk[p]<rnk[q])swap(p,q); if(rnk[p]==rnk[q]) rnk[p]++; par[q] = p; } 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]; return ; } long long mid = (l+r+1)/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); } } } 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-1,left); solve(mid,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,rnk[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 'void Union(long long int, long long int, long long int)':
plan.cpp:56:15: warning: unused variable 'parp' [-Wunused-variable]
   56 |     long long parp,parq;
      |               ^~~~
plan.cpp:56:20: warning: unused variable 'parq' [-Wunused-variable]
   56 |     long long parp,parq;
      |                    ^~~~
plan.cpp: In function 'int main()':
plan.cpp:141:15: warning: unused variable 'cnt' [-Wunused-variable]
  141 |     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...