Submission #171882

#	Time	Username	Problem	Language	Result	Execution time	Memory
171882		mosiashvililuka	Hard route (IZhO17_road)	C++14	19 / 100	2 ms	504 KiB

road

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,dp[109],dp2[109],msh[109],mxd[109],mshmxd[109],p[109],pi,i,j,dep[109],zx,xc,cnt,bo[109],pas1,pas2;
vector <int> v[109];
void dfs(int q, int w){
    dep[q]=dep[w]+1;
    msh[q]=w;
    for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        if((*it)==w) continue;
        dfs((*it),q);
        if(mxd[q]<mxd[(*it)]+1) mxd[q]=mxd[(*it)]+1;
    }
}
void dfs2(int q, int w){
    if(w!=0){
        mshmxd[q]=mshmxd[w]+1;
        for(vector <int>::iterator it=v[w].begin(); it!=v[w].end(); it++){
            if((*it)==msh[w]||(*it)==q) continue;
            if(mshmxd[q]<mxd[(*it)]+2) mshmxd[q]=mxd[(*it)]+2;
        }
    }
    for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        if((*it)==w) continue;
        dfs2((*it),q);
    }
}
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++){
            cnt++;
            c=p[i];d=p[j];
            bo[c]=cnt;bo[d]=cnt;
            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]||bo[(*it)]==cnt) continue;
                        if(xc<mxd[(*it)]+1) xc=mxd[(*it)]+1;
                    }
                    zx++;
                    c=msh[c];
                    bo[c]=cnt;
                }else{
                    for(vector <int>::iterator it=v[d].begin(); it!=v[d].end(); it++){
                        if((*it)==msh[d]||bo[(*it)]==cnt) continue;
                        if(xc<mxd[(*it)]+1) xc=mxd[(*it)]+1;
                    }
                    zx++;
                    d=msh[d];
                    bo[d]=cnt;
                }
            }
            if(xc<mshmxd[c]) xc=mshmxd[d];
            if(pas1<zx*xc){
                pas1=zx*xc;
                pas2=1;
            }else{
                if(pas1==zx*xc) pas2++;
            }
        }
    }
    cout<<pas1<<" "<<pas2;
    return 0;
}

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