/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Wrong Answer 5ms 2.812 MiB
#2 Wrong Answer 70ms 7.492 MiB
#3 Wrong Answer 69ms 7.539 MiB
#4 Wrong Answer 69ms 7.551 MiB
#5 Wrong Answer 68ms 7.418 MiB
#6 Wrong Answer 66ms 7.539 MiB
#7 Wrong Answer 66ms 7.535 MiB
#8 Wrong Answer 77ms 7.539 MiB
#9 Wrong Answer 71ms 7.535 MiB
#10 Wrong Answer 69ms 7.441 MiB
#11 Wrong Answer 59ms 7.34 MiB
#12 Wrong Answer 62ms 7.539 MiB
#13 Wrong Answer 59ms 7.352 MiB
#14 Wrong Answer 58ms 7.301 MiB
#15 Wrong Answer 57ms 7.406 MiB
#16 Wrong Answer 57ms 7.52 MiB
#17 Wrong Answer 59ms 7.332 MiB
#18 Wrong Answer 59ms 7.547 MiB
#19 Wrong Answer 59ms 7.332 MiB
#20 Wrong Answer 59ms 7.527 MiB
#21 Wrong Answer 4ms 2.824 MiB
#22 Wrong Answer 4ms 2.855 MiB
#23 Wrong Answer 43ms 16.438 MiB
#24 Wrong Answer 43ms 16.484 MiB
#25 Wrong Answer 4ms 2.816 MiB
#26 Wrong Answer 17ms 3.992 MiB

Code

#include<bits/stdc++.h>
using namespace std;
const long long M=1e5+10,MOD=1000000007;
typedef long long ll;
vector<int>e[M];
int level[M];
int lv[M];
int ans=1;
int target_distane=0;// using method re-rooting dp
int dp[M][2];
int vis[M];
vector<int>v;
void dfs1(int x,int p){
    for(int u:e[x]){
        if(u!=p){
            int cur_level=dp[x][0];
            if(dp[x][0]==level[u]+1)cur_level=dp[x][1];
            cur_level=max(cur_level,lv[x]);
            int total=cur_level+level[u];
            total/=2;
            lv[u]=cur_level+1;// root to down length
            if(total>=target_distane){
                if(total==target_distane){
                    if(cur_level==level[u])ans=max(ans,max(u,x));
                    else{
                        int dif=cur_level-level[u];
                        if(dif==1)ans=max(ans,x);
                        if(dif==-1)ans=max(ans,u);
                    }
                }
                else{
                    if(cur_level==level[u]){
                        ans=max(u,x);
                        target_distane=total;
                    }
                    else{
                        int dif=cur_level-level[u];
                        if(dif==1)ans=x,target_distane=total;
                        if(dif==-1)ans=u,target_distane=total;
                    }
            }
        }

            dfs1(u,x);
        }
    }
}
void dfs(int x,int p){
    dp[x][1]=dp[x][0]=1;
	vis[x]=1;
    for(int u:e[x]){
        if(vis[u]==0){
			vis[u]=1;
            dfs(u,x);
        }
    }
    if(p!=-1)
    level[p]=max(level[p],level[x]+1);
    if(p!=-1){
        int cur=level[x]+1;
       // v.push_back((int)dp[p][0]);
       // v.push_back((int)dp[p][1]);
        v.push_back((int)cur);
        sort(v.rbegin(),v.rend());
		v.clear();
        //dp[p][0]=1;// first max
        //dp[p][1]=1;//second max
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
     int n;
     cin>>n;
     for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
     }
     for(int i=1;i<=n;i++){
        level[i]=1;
		 dp[i][0]=0;
		 dp[i][1]=0;
     }
     dfs(1,-1);// lower level and upper level length
   // dfs1(1,0);
     cout<<target_distane<<" "<<ans<<"\n";
     
     
    }
    
   
   return 0;
    
}
 

Information

Submit By
Type
Submission
Problem
P1069 Vaccination
Language
C++11 (G++ 13.2.0)
Submit At
2024-07-11 17:49:29
Judged At
2024-10-03 13:41:35
Judged By
Score
0
Total Time
77ms
Peak Memory
16.484 MiB