Submission #171119

#	Time	Username	Problem	Language	Result	Execution time	Memory
171119		mosiashvililuka	Hard route (IZhO17_road)	C++14	0 / 100	13 ms	12152 KiB

road

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,p[500009],pi,i,j,dep[500009],mx[500009],msh[500009],pas,zx,xc,mxmsh[500009],pas2,ka[500009];
vector <int> v[500009];
void dfs(int q, int w){
    msh[q]=w;
    dep[q]=dep[w]+1;
    for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        if((*it)==w) continue;
        dfs((*it),q);
        if(mx[q]<mx[(*it)]+1) mx[q]=mx[(*it)]+1;
    }
}
void dfs2(int q, int w){
    for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        if((*it)==w) continue;
        dfs2((*it),q);
    }
    if(w!=0) mxmsh[q]=mxmsh[w]+1;
    if(w!=0){
        for(vector <int>::iterator it=v[w].begin(); it!=v[w].end(); it++){
            if((*it)==msh[w]||(*it)==q) continue;
            if(mxmsh[q]<mx[(*it)]+2) mxmsh[q]=mx[(*it)]+2;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a;
    for(b=1; b<a; b++){
        cin>>c>>d;
        v[c].push_back(d);
        v[d].push_back(c);
    }
    dfs(1,0);
    dfs2(1,0);
    for(b=1; b<=a; b++){
        if(v[b].size()==1){
            pi++;
            p[pi]=b;
        }
    }
    for(i=1; i<pi; i++){
        for(j=i+1; j<=pi; j++){
            c=p[i];d=p[j];
            e=i*(pi+4)+j;
            ka[c]=e;
            ka[d]=e;
            zx=0;xc=0;
            while(c!=d){
                if(dep[c]>=dep[d]){
                    for(vector <int>::iterator it=v[c].begin(); it!=v[c].end(); it++){
                        if((*it)==msh[c]||ka[(*it)]==e) continue;
                        if(xc<mx[(*it)]+1) xc=mx[(*it)]+1;
                    }
                    zx++;
                    ka[c]=e;
                    c=msh[c];
                }else{
                    for(vector <int>::iterator it=v[d].begin(); it!=v[d].end(); it++){
                        if((*it)==msh[d]||ka[(*it)]==e) continue;
                        if(xc<mx[(*it)]+1) xc=mx[(*it)]+1;
                    }
                    zx++;
                    ka[d]=e;
                    d=msh[d];
                }
            }
            if(xc<mxmsh[c]) xc=mxmsh[c];
     /*       if(p[i]==4&&p[j]==5){
                cout<<zx<<" "<<xc<<endl;
            }*/
/*            if(zx*xc==6){
                cout<<p[i]<<" "<<p[j]<<" "<<zx<<" "<<xc<<endl;
            }*/
            if(pas<zx*xc){
                pas=zx*xc;
                pas2=1;
            }else{
                if(pas==zx*xc) pas2++;
            }
        }
    }
  if(pas==0){
cout<<pas<<" "<<pi;
  return 0;}
    cout<<pas<<" "<<pas2;
    return 0;
}

• Subtask 1: 0 / 19
• Subtask 2: 0 / 33
• Subtask 3: 0 / 48