| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 168535 | mosiashvililuka | Evacuation plan (IZhO18_plan) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,zx,xc,i,j,za,z[1000009],tes,te,di[1000009],msh[1000009],dep[1000009],wv[1000009],pi,rmsh[1000009][18],mn[1000009][18],lf[1000009],rg[1000009],tim;
int bo[1000009];
vector <pair <int, int> > v[1000009];
pair <int, int> vv[1000009];
pair <int, pair <int, int> > qw[500009];
pair <int, int> f[1000009];
set <pair <int, int> > s;
set <pair <int, int> >::iterator t;
int fnd(int q){
if(msh[q]==0) return q; else return fnd(msh[q]);
}
void mrg(int q, int w, int r){
q=fnd(q);
w=fnd(w);
if(q==w) return;
if(dep[q]>dep[w]) swap(q,w);
pi++;
rmsh[wv[q]][0]=pi;
rmsh[wv[w]][0]=pi;
mn[wv[q]][0]=r;
mn[wv[w]][0]=r;
msh[q]=w;
vv[pi].first=wv[q];
vv[pi].second=wv[w];
wv[w]=pi;
dep[w]+=dep[q];
}
void dfs(int q){
bo[q]=i;
tim++;
rg[q]=lf[q]=tim;
if(vv[q].first==0) return;
dfs(vv[q].first);
dfs(vv[q].second);
if(rg[q]<rg[vv[q].first]) rg[q]=rg[vv[q].first];
if(rg[q]<rg[vv[q].second]) rg[q]=rg[vv[q].second];
}
bool anc(int q, int w){
if(lf[q]<=lf[w]&&rg[q]>=rg[w]) return 1; else return 0;
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a>>b;
for(i=1; i<=b; i++){
cin>>c>>d>>e;
qw[i].second.first=c;
qw[i].second.second=d;
v[c].push_back(make_pair(d,e));
v[d].push_back(make_pair(c,e));
}
cin>>za;
for(i=1; i<=a; i++) di[i]=1100000000;
for(i=1; i<=a; i++) for(j=0; j<=17; j++) mn[i][j]=1100000000;
for(i=1; i<=za; i++){
cin>>z[i];
di[z[i]]=0;
s.insert(make_pair(0,z[i]));
}
while(s.size()!=0){
d=(*s.begin()).first;
c=(*s.begin()).second;
s.erase(s.begin());
if(bo[c]==1) continue;
for(vector <pair <int, int> >::iterator it=v[c].begin(); it!=v[c].end(); it++){
if(di[(*it).first]>d+(*it).second){
di[(*it).first]=d+(*it).second;
s.insert(make_pair(di[(*it).first],(*it).first));
}
}
bo[c]=1;
}
for(i=1; i<=a; i++){
dep[i]=1;
wv[i]=i;
f[i].first=di[i];
f[i].second=i;
}
sort(f+1,f+a+1);
pi=a;
for(i=1; i<=b; i++) qw[i].first=min(di[qw[i].second.first],di[qw[i].second.second]);
sort(qw+1,qw+b+1);
for(i=b; i>=1; i--){
mrg(qw[i].second.first,qw[i].second.second,qw[i].first);
}
+ /*for(i=1; i<=a; i++){
c=f[i].second;
d=f[i].first;
for(vector <pair <int, long long> >::iterator it=v[c].begin(); it!=v[c].end(); it++){
mrg((*it).first,c,d);
}
}*/
for(i=pi; i>=1; i--){
bo[i]=0;
for(j=1; j<=17; j++){
rmsh[i][j]=rmsh[rmsh[i][j-1]][j-1];
mn[i][j]=min(mn[i][j-1],mn[rmsh[i][j-1]][j-1]);
}
}
for(i=pi; i>=1; i--){
if(bo[i]!=0) continue;
dfs(i);
}
cin>>tes;
for(te=1; te<=tes; te++){
cin>>c>>d;
zx=c;xc=d;
e=1100000000;
for(i=17; i>=0; i--){
if(rmsh[c][i]==0) continue;
if(anc(rmsh[c][i],d)==0){
if(e>mn[c][i]) e=mn[c][i];
c=rmsh[c][i];
}
}
if(e>mn[c][0]) e=mn[c][0];
c=rmsh[c][0];
c=d;
for(i=17; i>=0; i--){
if(rmsh[c][i]==0) continue;
if(anc(rmsh[c][i],d)==0){
if(e>mn[c][i]) e=mn[c][i];
c=rmsh[c][i];
}
}
if(e>mn[c][0]) e=mn[c][0];
c=rmsh[c][0];
cout<<e<<endl;
}
return 0;
}