oj.uz

Submission #171882

# Submission time Handle Problem Language Result Execution time Memory
171882 2019-12-30T14:51:31 Z mosiashvililuka Hard route (IZhO17_road) C++14
19 / 100
 2 ms 504 KB 
#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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Halted 0 ms 0 KB -