結果

問題 No.2531 Coloring Vertices on Namori
ユーザー 👑 AngrySadEight
提出日時 2023-10-19 01:28:19
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 235 ms / 2,000 ms
コード長 1,629 bytes
コンパイル時間 3,174 ms
コンパイル使用メモリ 162,356 KB
最終ジャッジ日時 2025-02-17 08:18:57
ジャッジサーバーID
(参考情報)
judge4 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <atcoder/all>
#include <cassert>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using namespace atcoder;
using ll = long long;
ll mod = 998244353;
int main() {
ll N, K;
cin >> N >> K;
vector<ll> u(N);
vector<ll> v(N);
for (ll i = 0; i < N; i++) {
cin >> u[i] >> v[i];
u[i]--;
v[i]--;
}
vector<ll> dist(N, N + 2);
queue<ll> que;
vector<vector<ll>> graph(N, vector<ll>(0));
dsu tree(N);
ll cnt = 0;
for (ll i = 0; i < N; i++) {
if (!tree.same(u[i], v[i])) {
graph[u[i]].push_back(v[i]);
graph[v[i]].push_back(u[i]);
tree.merge(u[i], v[i]);
} else {
que.push(u[i]);
dist[u[i]] = 0;
while (que.size()) {
ll p = que.front();
que.pop();
for (ll x : graph[p]) {
if (dist[x] < N) {
continue;
}
dist[x] = dist[p] + 1;
que.push(x);
}
}
cnt = dist[v[i]] + 1;
break;
}
}
vector<vector<ll>> dp(N, vector<ll>(2, 0));
dp[0][0] = K;
for (ll i = 1; i < N; i++) {
dp[i][0] = dp[i - 1][1];
dp[i][1] = (dp[i - 1][0] * (K - 1) + dp[i - 1][1] * (K - 2)) % mod;
}
ll ans = dp[cnt - 1][1];
for (ll i = 0; i < N - cnt; i++) {
ans = (ans * (K - 1)) % mod;
}
cout << ans << endl;
for (int i = 0; i < N; i++) {
assert(tree.same(0, i));
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0