提出 #69090797

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		vector<vector<int>>g(n);
		for(int i=1;i<n;i++){
			int p;
			cin>>p;
			p--;
			g[p].push_back(i);
		}
		auto dfs=[&](auto dfs,int u)->pair<int,int>{
			int S=0;
			int s=0,p=0;
			for(int v:g[u]){
				auto[sv,pv]=dfs(dfs,v);
				S+=sv;
				if(sv>s)s=sv,p=pv;
			}
			if(!S)return{1,0};
			int ans=0;
			if(s-p*2<=S-s)ans=S/2;
			else ans=S-s+p;
			S++;
			return{S,ans};
		};
		cout<<dfs(dfs,0).second<<'\n';
	}
}

提出情報

提出日時
問題 D - Non-Ancestor Matching
ユーザ Kagemeka
言語 C++ 20 (gcc 12.2)
得点 600
コード長 557 Byte
結果 AC
実行時間 178 ms
メモリ 47824 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 600 / 600
結果
AC × 1
AC × 87
セット名 テストケース
Sample 00_sample_00.txt
All 00_sample_00.txt, 01_small_00.txt, 01_small_01.txt, 01_small_02.txt, 02_handmade_00.txt, 02_handmade_01.txt, 02_handmade_02.txt, 02_handmade_03.txt, 02_handmade_04.txt, 02_handmade_05.txt, 02_handmade_06.txt, 02_handmade_07.txt, 02_handmade_08.txt, 02_handmade_09.txt, 02_handmade_10.txt, 02_handmade_11.txt, 02_handmade_12.txt, 02_handmade_13.txt, 02_handmade_14.txt, 02_handmade_15.txt, 02_handmade_16.txt, 02_handmade_17.txt, 02_handmade_18.txt, 02_handmade_19.txt, 02_handmade_20.txt, 02_handmade_21.txt, 02_handmade_22.txt, 02_handmade_23.txt, 02_handmade_24.txt, 02_handmade_25.txt, 02_handmade_26.txt, 02_handmade_27.txt, 02_handmade_28.txt, 02_handmade_29.txt, 02_handmade_30.txt, 02_handmade_31.txt, 02_handmade_32.txt, 02_handmade_33.txt, 02_handmade_34.txt, 02_handmade_35.txt, 02_handmade_36.txt, 02_handmade_37.txt, 02_handmade_38.txt, 02_handmade_39.txt, 02_handmade_40.txt, 02_handmade_41.txt, 02_handmade_42.txt, 02_handmade_43.txt, 02_handmade_44.txt, 02_handmade_45.txt, 03_random_00.txt, 03_random_01.txt, 03_random_02.txt, 03_random_03.txt, 03_random_04.txt, 03_random_05.txt, 03_random_06.txt, 03_random_07.txt, 03_random_08.txt, 03_random_09.txt, 03_random_10.txt, 03_random_11.txt, 03_random_12.txt, 03_random_13.txt, 03_random_14.txt, 03_random_15.txt, 03_random_16.txt, 03_random_17.txt, 03_random_18.txt, 03_random_19.txt, 03_random_20.txt, 03_random_21.txt, 03_random_22.txt, 03_random_23.txt, 03_random_24.txt, 03_random_25.txt, 03_random_26.txt, 04_from_path_subtree_01.txt, 04_from_path_subtree_02.txt, 04_from_path_subtree_03.txt, 04_from_path_subtree_04.txt, 04_from_path_subtree_05.txt, 04_from_path_subtree_06.txt, 04_from_path_subtree_07.txt, 04_from_path_subtree_08.txt, 04_from_path_subtree_09.txt, 04_from_path_subtree_10.txt
ケース名 結果 実行時間 メモリ
00_sample_00.txt AC 1 ms 3472 KiB
01_small_00.txt AC 94 ms 3472 KiB
01_small_01.txt AC 112 ms 3476 KiB
01_small_02.txt AC 107 ms 3608 KiB
02_handmade_00.txt AC 50 ms 16868 KiB
02_handmade_01.txt AC 116 ms 47824 KiB
02_handmade_02.txt AC 114 ms 31480 KiB
02_handmade_03.txt AC 113 ms 31388 KiB
02_handmade_04.txt AC 106 ms 22744 KiB
02_handmade_05.txt AC 107 ms 22616 KiB
02_handmade_06.txt AC 147 ms 36296 KiB
02_handmade_07.txt AC 165 ms 22888 KiB
02_handmade_08.txt AC 164 ms 23100 KiB
02_handmade_09.txt AC 165 ms 22940 KiB
02_handmade_10.txt AC 85 ms 3524 KiB
02_handmade_11.txt AC 86 ms 3592 KiB
02_handmade_12.txt AC 85 ms 3648 KiB
02_handmade_13.txt AC 85 ms 3464 KiB
02_handmade_14.txt AC 85 ms 3728 KiB
02_handmade_15.txt AC 86 ms 3592 KiB
02_handmade_16.txt AC 87 ms 3660 KiB
02_handmade_17.txt AC 87 ms 3540 KiB
02_handmade_18.txt AC 151 ms 23012 KiB
02_handmade_19.txt AC 87 ms 3604 KiB
02_handmade_20.txt AC 88 ms 3608 KiB
02_handmade_21.txt AC 88 ms 3556 KiB
02_handmade_22.txt AC 87 ms 3552 KiB
02_handmade_23.txt AC 79 ms 3552 KiB
02_handmade_24.txt AC 79 ms 3616 KiB
02_handmade_25.txt AC 79 ms 3624 KiB
02_handmade_26.txt AC 79 ms 3616 KiB
02_handmade_27.txt AC 84 ms 3600 KiB
02_handmade_28.txt AC 84 ms 3536 KiB
02_handmade_29.txt AC 84 ms 3604 KiB
02_handmade_30.txt AC 83 ms 3540 KiB
02_handmade_31.txt AC 114 ms 37916 KiB
02_handmade_32.txt AC 113 ms 39468 KiB
02_handmade_33.txt AC 116 ms 47716 KiB
02_handmade_34.txt AC 117 ms 47696 KiB
02_handmade_35.txt AC 117 ms 47784 KiB
02_handmade_36.txt AC 117 ms 47756 KiB
02_handmade_37.txt AC 117 ms 47764 KiB
02_handmade_38.txt AC 116 ms 47672 KiB
02_handmade_39.txt AC 116 ms 47720 KiB
02_handmade_40.txt AC 117 ms 47656 KiB
02_handmade_41.txt AC 123 ms 46092 KiB
02_handmade_42.txt AC 121 ms 44264 KiB
02_handmade_43.txt AC 119 ms 42664 KiB
02_handmade_44.txt AC 118 ms 40836 KiB
02_handmade_45.txt AC 58 ms 13436 KiB
03_random_00.txt AC 171 ms 22872 KiB
03_random_01.txt AC 173 ms 22872 KiB
03_random_02.txt AC 178 ms 22940 KiB
03_random_03.txt AC 168 ms 22916 KiB
03_random_04.txt AC 170 ms 22972 KiB
03_random_05.txt AC 164 ms 22956 KiB
03_random_06.txt AC 168 ms 22864 KiB
03_random_07.txt AC 169 ms 22900 KiB
03_random_08.txt AC 170 ms 22940 KiB
03_random_09.txt AC 174 ms 22864 KiB
03_random_10.txt AC 52 ms 17008 KiB
03_random_11.txt AC 53 ms 17060 KiB
03_random_12.txt AC 61 ms 18140 KiB
03_random_13.txt AC 74 ms 17868 KiB
03_random_14.txt AC 84 ms 3460 KiB
03_random_15.txt AC 84 ms 3532 KiB
03_random_16.txt AC 84 ms 3536 KiB
03_random_17.txt AC 84 ms 3544 KiB
03_random_18.txt AC 84 ms 3524 KiB
03_random_19.txt AC 133 ms 31896 KiB
03_random_20.txt AC 132 ms 31860 KiB
03_random_21.txt AC 135 ms 31916 KiB
03_random_22.txt AC 145 ms 34860 KiB
03_random_23.txt AC 146 ms 34800 KiB
03_random_24.txt AC 153 ms 34828 KiB
03_random_25.txt AC 151 ms 34840 KiB
03_random_26.txt AC 152 ms 34760 KiB
04_from_path_subtree_01.txt AC 131 ms 35772 KiB
04_from_path_subtree_02.txt AC 124 ms 39796 KiB
04_from_path_subtree_03.txt AC 121 ms 42948 KiB
04_from_path_subtree_04.txt AC 130 ms 37484 KiB
04_from_path_subtree_05.txt AC 121 ms 41096 KiB
04_from_path_subtree_06.txt AC 119 ms 45920 KiB
04_from_path_subtree_07.txt AC 123 ms 39232 KiB
04_from_path_subtree_08.txt AC 122 ms 42400 KiB
04_from_path_subtree_09.txt AC 131 ms 36364 KiB
04_from_path_subtree_10.txt AC 121 ms 45928 KiB