提出 #59412864

ソースコード 拡げる

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	int w=1,s=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch)){s=s*10+(ch-'0');ch=getchar();}
	return w*s;
}
const int mod=998244353;
const int maxn=3e5+100;
const int inf=3e17+7;
int n,du[maxn];
bool vis[maxn];
int ans=0,sum=0;
vector<int> G[maxn];
void dfs(int x)
{
	for(auto y : G[x])
	{
		if(vis[y])continue;
		if(du[y]==3)
		{
			vis[y]=1;
			dfs(y);
		}
		else if(du[y]==2)sum++;
	}
}
signed main()
{
#ifdef Lydic
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
// #else
//     freopen("chess.in","r",stdin);
//     freopen("chess.out","w",stdout);
#endif
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();
		G[x].push_back(y);G[y].push_back(x);
		du[x]++;du[y]++;
	}
	for(int i=1;i<=n;i++)
	{
		if(du[i]!=3||vis[i])continue;
		sum=0;vis[i]=1;
		dfs(i);
		ans+=(sum-1)*sum/2;
	}
	cout<<ans;
	return 0;
}

提出情報

提出日時
問題 F - Add One Edge 2
ユーザ Lydic
言語 C++ 20 (gcc 12.2)
得点 500
コード長 1014 Byte
結果 AC
実行時間 56 ms
メモリ 19240 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 500 / 500
結果
AC × 3
AC × 39
セット名 テストケース
Sample 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_test_01.txt, 01_test_02.txt, 01_test_03.txt, 01_test_04.txt, 01_test_05.txt, 01_test_06.txt, 01_test_07.txt, 01_test_08.txt, 01_test_09.txt, 01_test_10.txt, 01_test_11.txt, 01_test_12.txt, 01_test_13.txt, 01_test_14.txt, 01_test_15.txt, 01_test_16.txt, 01_test_17.txt, 01_test_18.txt, 01_test_19.txt, 01_test_20.txt, 01_test_21.txt, 01_test_22.txt, 01_test_23.txt, 01_test_24.txt, 01_test_25.txt, 01_test_26.txt, 01_test_27.txt, 01_test_28.txt, 01_test_29.txt, 01_test_30.txt, 01_test_31.txt, 01_test_32.txt, 01_test_33.txt, 01_test_34.txt, 01_test_35.txt, 02_hand_01.txt
ケース名 結果 実行時間 メモリ
00_sample_01.txt AC 2 ms 3448 KiB
00_sample_02.txt AC 2 ms 3492 KiB
00_sample_03.txt AC 2 ms 3496 KiB
01_test_01.txt AC 49 ms 17888 KiB
01_test_02.txt AC 48 ms 17936 KiB
01_test_03.txt AC 48 ms 18000 KiB
01_test_04.txt AC 47 ms 17896 KiB
01_test_05.txt AC 47 ms 17908 KiB
01_test_06.txt AC 50 ms 17920 KiB
01_test_07.txt AC 48 ms 17872 KiB
01_test_08.txt AC 49 ms 17872 KiB
01_test_09.txt AC 48 ms 17920 KiB
01_test_10.txt AC 49 ms 17936 KiB
01_test_11.txt AC 48 ms 18016 KiB
01_test_12.txt AC 52 ms 17820 KiB
01_test_13.txt AC 47 ms 17892 KiB
01_test_14.txt AC 50 ms 17892 KiB
01_test_15.txt AC 56 ms 17808 KiB
01_test_16.txt AC 7 ms 5652 KiB
01_test_17.txt AC 40 ms 15772 KiB
01_test_18.txt AC 10 ms 6744 KiB
01_test_19.txt AC 22 ms 10584 KiB
01_test_20.txt AC 15 ms 8088 KiB
01_test_21.txt AC 30 ms 19240 KiB
01_test_22.txt AC 30 ms 19128 KiB
01_test_23.txt AC 29 ms 19184 KiB
01_test_24.txt AC 32 ms 19120 KiB
01_test_25.txt AC 30 ms 19132 KiB
01_test_26.txt AC 42 ms 17416 KiB
01_test_27.txt AC 41 ms 17376 KiB
01_test_28.txt AC 42 ms 17384 KiB
01_test_29.txt AC 39 ms 17376 KiB
01_test_30.txt AC 44 ms 17408 KiB
01_test_31.txt AC 41 ms 17440 KiB
01_test_32.txt AC 41 ms 17420 KiB
01_test_33.txt AC 41 ms 17384 KiB
01_test_34.txt AC 43 ms 17384 KiB
01_test_35.txt AC 41 ms 17376 KiB
02_hand_01.txt AC 23 ms 17268 KiB