提出 #73696368

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int p = 998244353;

ll Pow(ll a, ll b) {
	ll res = 1;
	for ( ; b ; b >>= 1) {
		if (b & 1) res = res * a % p;
		a = a * a % p;
	}
	return res;
}

int n, m;
int u[200010], v[200010];
int f[200010], tot;

int find(int p) {
	if (f[p] == p) return p;
	return f[p] = find(f[p]);
}

int main() {
	cin >> n >> m;
	for (int i = 1 ; i <= m ; i++) cin >> u[i] >> v[i];
	tot = n;
	for (int i = 1 ; i <= n ; i++) f[i] = i;
	ll ans = 0;
	for (int i = m ; i ; i--) {
		u[i] = find(u[i]), v[i] = find(v[i]);
		if (u[i] != v[i]) {
			if (tot == 2) ans = (ans + Pow(2, i)) % p;
			else f[u[i]] = v[i], --tot;
		}
//		cout << tot << "     ";
//		for (int i = 1 ; i <= n ; i++) cout << f[i] << " "; puts("");
	}
	cout << ans << endl;
	return 0;
}

提出情報

提出日時
問題 E - Divide Graph
ユーザ dongzirui0817
言語 C++ IOI-Style(GNU++20) (GCC 14.2.0)
得点 475
コード長 843 Byte
結果 AC
実行時間 60 ms
メモリ 4008 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 475 / 475
結果
AC × 3
AC × 36
セット名 テストケース
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 02_perfect_00.txt, 02_perfect_01.txt, 02_perfect_02.txt, 02_perfect_03.txt, 02_perfect_04.txt, 02_perfect_05.txt, 02_perfect_06.txt, 02_perfect_07.txt, 02_perfect_08.txt, 03_tree_00.txt, 03_tree_01.txt, 03_tree_02.txt, 03_tree_03.txt, 03_tree_04.txt, 03_tree_05.txt, 03_tree_06.txt, 04_handmade_00.txt, 04_handmade_01.txt
ケース名 結果 実行時間 メモリ
00_sample_00.txt AC 0 ms 1704 KiB
00_sample_01.txt AC 0 ms 1704 KiB
00_sample_02.txt AC 0 ms 1704 KiB
01_random_00.txt AC 38 ms 3112 KiB
01_random_01.txt AC 34 ms 2856 KiB
01_random_02.txt AC 30 ms 2728 KiB
01_random_03.txt AC 3 ms 1832 KiB
01_random_04.txt AC 36 ms 2984 KiB
01_random_05.txt AC 32 ms 2728 KiB
01_random_06.txt AC 26 ms 2600 KiB
01_random_07.txt AC 25 ms 2472 KiB
01_random_08.txt AC 38 ms 2984 KiB
01_random_09.txt AC 27 ms 2600 KiB
01_random_10.txt AC 58 ms 3880 KiB
01_random_11.txt AC 56 ms 3880 KiB
01_random_12.txt AC 60 ms 4008 KiB
01_random_13.txt AC 38 ms 3112 KiB
01_random_14.txt AC 51 ms 3752 KiB
02_perfect_00.txt AC 39 ms 3240 KiB
02_perfect_01.txt AC 40 ms 3240 KiB
02_perfect_02.txt AC 40 ms 3240 KiB
02_perfect_03.txt AC 44 ms 3240 KiB
02_perfect_04.txt AC 40 ms 3240 KiB
02_perfect_05.txt AC 45 ms 3240 KiB
02_perfect_06.txt AC 40 ms 3240 KiB
02_perfect_07.txt AC 40 ms 3240 KiB
02_perfect_08.txt AC 40 ms 3240 KiB
03_tree_00.txt AC 58 ms 4008 KiB
03_tree_01.txt AC 58 ms 4008 KiB
03_tree_02.txt AC 56 ms 4008 KiB
03_tree_03.txt AC 59 ms 4008 KiB
03_tree_04.txt AC 58 ms 4008 KiB
03_tree_05.txt AC 59 ms 4008 KiB
03_tree_06.txt AC 58 ms 4008 KiB
04_handmade_00.txt AC 0 ms 1704 KiB
04_handmade_01.txt AC 56 ms 4008 KiB