Submission #738104

#	Time	Username	Problem	Language	Result	Execution time	Memory
738104		mosiashvililuka	Roadside Advertisements (NOI17_roadsideadverts)	C++14	100 / 100	56 ms	11600 KiB

roadsideadverts

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,pas,dep[50009],lf[50009],rg[50009],tim,msh[50009][19],pi;
vector <pair <int, int> > v[50009];
pair <int, int> p[9];
void dfsst(int q, int w){
    tim++;
    lf[q]=rg[q]=tim;
    msh[q][0]=w;
    for(int h=1; h<=17; h++){
        msh[q][h]=msh[msh[q][h-1]][h-1];
    }
    for(vector <pair <int, int> >::iterator it=v[q].begin(); it!=v[q].end(); it++){
        if((*it).first==w) continue;
        dep[(*it).first]=dep[q]+(*it).second;
        dfsst((*it).first,q);
        if(rg[q]<rg[(*it).first]) rg[q]=rg[(*it).first];
    }
}
bool anc(int q, int w){
    if(lf[q]<=lf[w]&&rg[q]>=rg[w]) return 1; else return 0;
}
int lca(int q, int w){
    if(anc(q,w)) return q;
    if(anc(w,q)) return w;
    for(int h=17; h>=0; h--){
        if(msh[q][h]==0||anc(msh[q][h],w)==1) continue;
        q=msh[q][h];
    }
    return msh[q][0];
}
int dista(int q, int w){
    return dep[q]+dep[w]-dep[lca(q,w)]*2;
}
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a;
    for(i=1; i<a; i++){
        cin>>c>>d>>e;c++;d++;
        v[c].push_back({d,e});
        v[d].push_back({c,e});
    }
    dfsst(1,0);
    cin>>tes;
    for(t=1; t<=tes; t++){
        pi=5;
        for(i=1; i<=pi; i++){
            cin>>p[i].second;p[i].second++;
            p[i].first=lf[p[i].second];
        }
        sort(p+1,p+pi+1);
        p[pi+1]=p[1];pas=0;
        for(i=1; i<=pi; i++){
            pas+=dista(p[i].second,p[i+1].second);
        }
        pas/=2;
        cout<<pas<<"\n";
    }
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 40 / 40
• Subtask 4: 30 / 30