提出 #34665160

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/dsu>
using mint = atcoder::modint998244353;
using namespace std;

#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}

int k;
vector<vector<int>> to; // to[树的节点] = vector<叶子节点>
vector<mint> merge(const vector<mint>& d, const vector<mint>& e) { // 就暴力merge, 卷积
  vector<mint> dp(d.size() + e.size() - 1);
  rep(i,0,d.size())rep(j,0,e.size()) dp[i+j] += d[i]*e[j];
  if ((int)dp.size() > k+1) dp.resize(k+1);
  return dp;
};

vector<mint> dfs (int v) { // 树节点v
  vector<mint> dp = {1,0}; // dp[i]:  <=i-1次不行,i次才行的染色集合方案数, 可以写成{1,0}后面需要加 if(dp.size() == 1) dp.resize(2);,这里丢个0, 省去resize
  for (int u : to[v]) dp = merge(dfs(u),dp);
  int c = to[v].size(); // 子节点个数
  if (c != 0 && c < (int)dp.size()) dp[c] -= 1; // 每个子节点选一次, 全部染色的情况
  dp[1] += 1; // 直接染v
  return dp;
};

int top[100010]; // top[并查集根] = to上树的节点

int main() {
  int n = read();
  int m = read();
  k = read();
  map<int,vector<pair<int,int> >> mp;
  rep(i,0,m) {
    int a = read()-1;
    int b = read()-1;
    int c = read();
    mp[c].push_back({a,b});
  }
  to.resize(n);
  iota(top,top+n,0); // 初始每个根是自己 top[i] = i
  vector<bool> root(n,true); // 是否是树上目前的根节点

  // 建树
  atcoder::dsu t(n); // 并查集
  for (auto [_,es] : mp) { // 边从小到大
    set<int> st; // 哪些根是这轮合并的
    for (auto [a,b] : es) {
      a = t.leader(a); // 并查集根
      b = t.leader(b);
      if (a == b) continue;
      t.merge(a,b); // 合并 并查集
      st.insert(a);
      st.insert(b);
    }
    for (int v : st) if(v == t.leader(v)){ // 找到每组内部的根
      root[top[v]] = false; // top[v] 不再是根
      to.push_back(vector<int>(1,top[v])); // 新节点[] -> 树上叶子节点
      root.push_back(true); // root[to.size()-1] = true, 和to的sz一致
      top[v] = to.size()-1; // v的目前对应树上节点
    }
    for (int v : st) if(v != t.leader(v)){ // 非根的部分
      int p = t.leader(v); // p 是并查集跟
      root[top[v]] = false; // v不再是树根
      to[top[p]].push_back(top[v]); // 树节点指向vector<子节点>
    }
  }
  // dp on tree
  vector<mint> dp = {1};
  rep(i,0,root.size()) if (root[i]) dp = merge(dp,dfs(i));
  mint ans;
  rep(i,0,dp.size()) ans += dp[i];
  printf("%d\n",ans.val());
  return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘int read()’:
./Main.cpp:8:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    8 | int read(){int r;scanf("%d",&r);return r;}
      |                  ~~~~~^~~~~~~~~

ジャッジ結果