結果

問題 No.2531 Coloring Vertices on Namori
ユーザー ococonomy1
提出日時 2023-11-03 22:45:10
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 271 ms / 2,000 ms
コード長 7,355 bytes
コンパイル時間 1,706 ms
コンパイル使用メモリ 127,548 KB
最終ジャッジ日時 2025-02-17 18:38:33
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

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

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define TEST cerr << "TEST" << endl
#define AMARI 998244353
// #define AMARI 1000000007
#define TIME_LIMIT 1980000
#define el '\n'
#define El '\n'
class ococo_unionfind {
//
//
//
//
//
//
//
public:
ococo_unionfind(int n = 0) {
for(int i = 0; i < n; i++) vinsert();
}
int simakosuu = 0;
// g[i] = {,rank}
// rank:
vector<pair<int, int>> g;
// rs[i] =
//
vector<int> rs;
// O(1)
void vinsert(void) {
g.emplace_back(g.size(), 1);
simakosuu++;
rs.push_back(1);
}
// O(α(N))
int ne(int a) {
if(g[a].first == a) return a;
else {
return g[a].first = ne(g[a].first);
}
}
// O(logN)
void einsert(int a, int b) {
if(a != b) {
int a1 = ne(a), a2 = ne(b);
if(a1 != a2) {
simakosuu--;
int rs12sum = rs[a1] + rs[a2];
rs[a1] = rs12sum;
rs[a2] = rs12sum;
if(g[a1].second < g[a2].second) {
g[a1].first = a2;
g[a2].second = max(g[a1].second + 1, g[a2].second);
} else {
g[a2].first = a1;
g[a1].second = max(g[a2].second + 1, g[a1].second);
}
}
}
}
void peinsert(pair<int,int> p){
einsert(p.first,p.second);
return;
}
// 2 O(α(N))
bool renketucheck(int a, int b) {
if(ne(a) == ne(b)) return true;
else return false;
}
bool prenketucheck(pair<int,int> p){
return renketucheck(p.first,p.second);
}
// O(1)
int islandnum(void) {
return simakosuu;
}
//
// O(α(N))
int islandsize(int a) {
return rs[ne(a)];
}
};
// union-find
class ococo_namori_graph {
private:
public:
int n;
ococo_unionfind ngouf;
vector<vector<int>> g, tree;
vector<bool> is_loop, visited;
vector<int> bubunki_oya;
bool rk = false;
//
vector<int> loop_seibun;
// ococo_namori_graph(n)n O(N)
ococo_namori_graph(int N = 0) {
n = N;
g.resize(n);
is_loop.resize(n);
visited.resize(n);
for(int i = 0; i < n; i++) {
is_loop[i] = false;
visited[i] = false;
}
bubunki_oya.resize(n);
for(int i = 0; i < n; i++) ngouf.vinsert();
rk = false;
}
// uv O(α(N)) O(N)
void einsert(int u, int v) {
if(!rk) {
if(ngouf.renketucheck(u, v)) {
rk = true;
// uBFS
// vloop
//{,}
queue<pair<int, int>> que;
que.push({u, -1});
vector<int> mae(n, -1);
bool flag = false;
while(!que.empty()) {
pair<int, int> temp = que.front();
que.pop();
// clog << temp.first << endl;
for(int i = 0; i < g[temp.first].size(); i++) {
if(mae[g[temp.first][i]] != -1) continue;
que.push({g[temp.first][i], temp.first});
mae[g[temp.first][i]] = temp.first;
if(g[temp.first][i] == v) {
flag = true;
break;
}
}
if(flag) break;
}
int temp = v;
loop_seibun.push_back(temp);
is_loop[temp] = true;
while(temp != u) {
temp = mae[temp];
loop_seibun.push_back(temp);
is_loop[temp] = true;
}
tree.resize(loop_seibun.size());
}
ngouf.einsert(u, v);
}
g[u].push_back(v);
g[v].push_back(u);
}
// O(N)
void tree_kettei(void) {
if(loop_seibun.size() == 0) return;
for(int i = 0; i < loop_seibun.size(); i++) {
queue<int> que;
que.push(loop_seibun[i]);
bubunki_oya[loop_seibun[i]] = i;
while(!que.empty()) {
int temp = que.front();
que.pop();
for(int j = 0; j < g[temp].size(); j++) {
if(visited[g[temp][j]] || is_loop[g[temp][j]]) continue;
visited[g[temp][j]] = true;
que.push(g[temp][j]);
bubunki_oya[g[temp][j]] = i;
}
}
}
}
};
#define MULTI_TEST_CASE false
void solve(void) {
int n;
ll k;
cin >> n >> k;
vector<vector<int>> g(n);
ococo_namori_graph ng(n);
for(int i = 0; i < n; i++){
int u,v;
cin >> u >> v;
u--; v--;
g[u].push_back(v);
g[v].push_back(u);
ng.einsert(u,v);
}
int m = ng.loop_seibun.size();
//1dp0dp1
vector<ll> dp0(m,0),dp1(m,0);
dp0[0] = 1;
for(int i = 1; i < m; i++){
dp0[i] = dp1[i - 1];
dp1[i] = dp0[i - 1] * (k - 1) + dp1[i - 1] * (k - 2);
dp1[i] %= AMARI;
}
ll ans = dp1.back();
for(int i = 0; i < (n - m); i++){
ans *= (k - 1);
ans %= AMARI;
}
//dp0
ans *= k;
ans %= AMARI;
cout << ans << el;
return;
}
void calc(void) {
return;
}
signed main(void) {
cin.tie(nullptr);
ios::sync_with_stdio(false);
calc();
int t = 1;
if(MULTI_TEST_CASE) cin >> t;
while(t--) {
solve();
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0