Submission #73683549

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define rep(t,l,r) for(int t=l;t<=r;t++)
#define per(t,l,r) for(int t=r;t>=l;t--)
const int N=200005;
int h[N],e[N*2],n[N*2],ct,d[N],f[N],a;
void add(int u,int v){e[++ct]=v;n[ct]=h[u];h[u]=ct;d[u]++;}
void dfs(int u,int p){
    int m1=0,m2=0; if(d[u]>=2) a=max(a,1);
    for(int i=h[u];i;i=n[i]){
        int v=e[i]; if(v==p) continue;
        dfs(v,u);
        if(d[u]>=4){
            if(f[v]>m1) m2=m1,m1=f[v];
            else if(f[v]>m2) m2=f[v];
        } else if(d[u]==3) a=max(a,f[v]+1);
    }
    if(d[u]>=4) f[u]=m1+1,a=max(a,m1+m2+1);
    else f[u]=(d[u]==3?1:0);
}
void solve(){
    int n_pt; cin>>n_pt; ct=a=0;
    rep(i,1,n_pt) h[i]=d[i]=f[i]=0;
    rep(i,1,n_pt-1){ int u,v; cin>>u>>v; add(u,v); add(v,u); }
    dfs(1,0); cout<<a<<"\n";
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int q; cin>>q; while(q--) solve();
    return 0;
}

Submission Info

Submission Time
Task F - Centipede Graph
User Fourier_WJY
Language C++ IOI-Style(GNU++20) (GCC 14.2.0)
Score 500
Code Size 937 Byte
Status AC
Exec Time 32 ms
Memory 11020 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 1
AC × 47
Set Name Test Cases
Sample 00_sample_00.txt
All 00_sample_00.txt, 01_small_00.txt, 01_small_01.txt, 01_small_02.txt, 01_small_03.txt, 01_small_04.txt, 01_small_05.txt, 01_small_06.txt, 02_random_00.txt, 02_random_01.txt, 02_random_02.txt, 02_random_03.txt, 02_random_04.txt, 02_random_05.txt, 02_random_06.txt, 02_random_07.txt, 03_path_00.txt, 03_path_01.txt, 03_path_02.txt, 03_path_03.txt, 03_path_04.txt, 03_path_05.txt, 03_path_06.txt, 03_path_07.txt, 03_path_08.txt, 03_path_09.txt, 04_star_00.txt, 04_star_01.txt, 04_star_02.txt, 05_uni_00.txt, 05_uni_01.txt, 05_uni_02.txt, 05_uni_03.txt, 05_uni_04.txt, 05_uni_05.txt, 06_bi-ternary_00.txt, 06_bi-ternary_01.txt, 06_bi-ternary_02.txt, 06_bi-ternary_03.txt, 06_bi-ternary_04.txt, 06_bi-ternary_05.txt, 06_bi-ternary_06.txt, 06_bi-ternary_07.txt, 06_bi-ternary_08.txt, 06_bi-ternary_09.txt, 06_bi-ternary_10.txt, 06_bi-ternary_11.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 0 ms 1676 KiB
01_small_00.txt AC 13 ms 1676 KiB
01_small_01.txt AC 13 ms 1676 KiB
01_small_02.txt AC 13 ms 1676 KiB
01_small_03.txt AC 13 ms 1676 KiB
01_small_04.txt AC 13 ms 1676 KiB
01_small_05.txt AC 13 ms 1676 KiB
01_small_06.txt AC 8 ms 1676 KiB
02_random_00.txt AC 14 ms 1804 KiB
02_random_01.txt AC 14 ms 1804 KiB
02_random_02.txt AC 14 ms 1804 KiB
02_random_03.txt AC 30 ms 6540 KiB
02_random_04.txt AC 20 ms 4364 KiB
02_random_05.txt AC 25 ms 5644 KiB
02_random_06.txt AC 23 ms 5004 KiB
02_random_07.txt AC 20 ms 4236 KiB
03_path_00.txt AC 12 ms 1804 KiB
03_path_01.txt AC 13 ms 1804 KiB
03_path_02.txt AC 14 ms 2188 KiB
03_path_03.txt AC 14 ms 2188 KiB
03_path_04.txt AC 18 ms 5388 KiB
03_path_05.txt AC 18 ms 5260 KiB
03_path_06.txt AC 32 ms 10380 KiB
03_path_07.txt AC 30 ms 11020 KiB
03_path_08.txt AC 29 ms 10252 KiB
03_path_09.txt AC 29 ms 9868 KiB
04_star_00.txt AC 18 ms 7180 KiB
04_star_01.txt AC 12 ms 1932 KiB
04_star_02.txt AC 15 ms 4364 KiB
05_uni_00.txt AC 13 ms 1804 KiB
05_uni_01.txt AC 14 ms 1932 KiB
05_uni_02.txt AC 17 ms 4108 KiB
05_uni_03.txt AC 27 ms 7180 KiB
05_uni_04.txt AC 27 ms 7180 KiB
05_uni_05.txt AC 27 ms 7180 KiB
06_bi-ternary_00.txt AC 25 ms 7180 KiB
06_bi-ternary_01.txt AC 15 ms 3980 KiB
06_bi-ternary_02.txt AC 12 ms 1804 KiB
06_bi-ternary_03.txt AC 26 ms 7180 KiB
06_bi-ternary_04.txt AC 16 ms 3852 KiB
06_bi-ternary_05.txt AC 12 ms 1804 KiB
06_bi-ternary_06.txt AC 25 ms 7180 KiB
06_bi-ternary_07.txt AC 16 ms 4108 KiB
06_bi-ternary_08.txt AC 12 ms 1804 KiB
06_bi-ternary_09.txt AC 26 ms 7180 KiB
06_bi-ternary_10.txt AC 16 ms 3468 KiB
06_bi-ternary_11.txt AC 12 ms 1804 KiB