#936350 (C++14) No.1333 Squared Sum

提出ソース

結果

問題	No.1333 Squared Sum
ユーザー	miyo2580
提出日時	2023-12-04 23:22:09
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,077 ms / 2,000 ms
コード長	6,427 bytes
コンパイル時間	2,311 ms
コンパイル使用メモリ	193,600 KB
実行使用メモリ	148,992 KB
最終ジャッジ日時	2024-09-26 23:21:07
合計ジャッジ時間	28,202 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	807 ms 52,608 KB
testcase_04	AC	792 ms 52,608 KB
testcase_05	AC	779 ms 52,608 KB
testcase_06	AC	780 ms 52,608 KB
testcase_07	AC	788 ms 52,608 KB
testcase_08	AC	819 ms 52,480 KB
testcase_09	AC	811 ms 52,736 KB
testcase_10	AC	812 ms 52,608 KB
testcase_11	AC	805 ms 52,736 KB
testcase_12	AC	814 ms 52,608 KB
testcase_13	AC	598 ms 148,992 KB
testcase_14	AC	995 ms 101,248 KB
testcase_15	AC	1,027 ms 137,216 KB
testcase_16	AC	2 ms 5,376 KB
testcase_17	AC	2 ms 5,376 KB
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	2 ms 5,376 KB
testcase_22	AC	2 ms 5,376 KB
testcase_23	AC	2 ms 5,376 KB
testcase_24	AC	2 ms 5,376 KB
testcase_25	AC	2 ms 5,376 KB
testcase_26	AC	1,077 ms 146,560 KB
testcase_27	AC	988 ms 103,808 KB
testcase_28	AC	1,029 ms 145,536 KB
testcase_29	AC	585 ms 148,992 KB
testcase_30	AC	271 ms 24,064 KB
testcase_31	AC	139 ms 15,104 KB
testcase_32	AC	414 ms 33,024 KB
testcase_33	AC	322 ms 26,880 KB
testcase_34	AC	597 ms 43,008 KB
testcase_35	AC	457 ms 33,408 KB
testcase_36	AC	236 ms 21,248 KB
testcase_37	AC	238 ms 22,016 KB
testcase_38	AC	285 ms 24,960 KB
testcase_39	AC	509 ms 37,376 KB
testcase_40	AC	887 ms 68,640 KB
testcase_41	AC	868 ms 68,640 KB
testcase_42	AC	893 ms 68,772 KB
testcase_43	AC	853 ms 68,644 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In lambda function:
main.cpp:226:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  226 |       auto[a,b,c]=x;
      |           ^
main.cpp:227:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  227 |       auto[A,B,C]=y;
      |           ^
main.cpp: In lambda function:
main.cpp:234:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  234 |       auto[a,b,c]=x;
      |           ^

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (ll i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
using Graph = vector<vector<ll>>;
const long long INF = 1LL<<60;
const long long MOD = 1000000007;

//https://nyaannyaan.github.io/library/graph/graph-template.hpp
template <typename T>
struct edge {
  int src, to;
  T cost;

  edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {}
  edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
using UnweightedGraph = vector<vector<int>>;

// Input of (Unweighted) Graph
UnweightedGraph graph(int N, int M = -1, bool is_directed = false,
                      bool is_1origin = true) {
  UnweightedGraph g(N);
  if (M == -1) M = N - 1;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    if (is_1origin) x--, y--;
    g[x].push_back(y);
    if (!is_directed) g[y].push_back(x);
  }
  return g;
}

// Input of Weighted Graph
template <typename T>
WeightedGraph<T> wgraph(int N, int M = -1, bool is_directed = false,
                        bool is_1origin = true) {
  WeightedGraph<T> g(N);
  if (M == -1) M = N - 1;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    cin >> c;
    if (is_1origin) x--, y--;
    g[x].emplace_back(x, y, c);
    if (!is_directed) g[y].emplace_back(y, x, c);
  }
  return g;
}

// Input of Edges
template <typename T>
Edges<T> esgraph(int N, int M, int is_weighted = true, bool is_1origin = true) {
  Edges<T> es;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    if (is_weighted)
      cin >> c;
    else
      c = 1;
    if (is_1origin) x--, y--;
    es.emplace_back(x, y, c);
  }
  return es;
}

// Input of Adjacency Matrix
template <typename T>
vector<vector<T>> adjgraph(int N, int M, T INF, int is_weighted = true,
                           bool is_directed = false, bool is_1origin = true) {
  vector<vector<T>> d(N, vector<T>(N, INF));
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    if (is_weighted)
      cin >> c;
    else
      c = 1;
    if (is_1origin) x--, y--;
    d[x][y] = c;
    if (!is_directed) d[y][x] = c;
  }
  return d;
}

/**
 * @brief グラフテンプレート
 * @docs docs/graph/graph-template.md
 */

//https://nyaannyaan.github.io/library/tree/rerooting.hpp

// Rerooting
// f1(c1, c2) ... merge value of child node
// f2(memo[i], chd, par) ... return value from child node to parent node
// memo[i] ... result of subtree rooted i
// dp[i] ... result of tree rooted i
template <typename T, typename G, typename F1, typename F2>
struct Rerooting {
  const G &g;
  const F1 f1;
  const F2 f2;
  vector<T> memo, dp;
  T I;

  Rerooting(const G &_g, const F1 _f1, const F2 _f2, const T &I_)
      : g(_g), f1(_f1), f2(_f2), memo(g.size(), I_), dp(g.size(), I_), I(I_) {
    dfs(0, -1);
    efs(0, -1, I);
  }

  const T &operator[](int i) const { return dp[i]; }

  void dfs(int cur, int par) {
    for (auto &dst : g[cur]) {
      if (dst == par) continue;
      dfs(dst, cur);
      memo[cur] = f1(memo[cur], f2(memo[dst], dst, cur));
    }
  }

  void efs(int cur, int par, const T &pval) {
    // get cumulative sum
    vector<T> buf;
    for (auto dst : g[cur]) {
      if (dst == par) continue;
      buf.push_back(f2(memo[dst], dst, cur));
    }
    vector<T> head(buf.size() + 1), tail(buf.size() + 1);
    head[0] = tail[buf.size()] = I;
    for (int i = 0; i < (int)buf.size(); i++) head[i + 1] = f1(head[i], buf[i]);
    for (int i = (int)buf.size() - 1; i >= 0; i--)
      tail[i] = f1(tail[i + 1], buf[i]);

    // update
    dp[cur] = par == -1 ? head.back() : f1(pval, head.back());

    // propagate
    int idx = 0;
    for (auto &dst : g[cur]) {
      if (dst == par) continue;
      efs(dst, cur, f2(f1(pval, f1(head[idx], tail[idx + 1])), cur, dst));
      idx++;
    }
  }
};

/**
 * @brief Rerooting(全方位木DP)
 * @docs docs/tree/rerooting.md
 */

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

using F=tuple<mint,mint,mint> ;

int main()
{  
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n;cin>>n;
    auto g=wgraph<ll>(n,n-1,0,1);
    map<P,ll> mp;
    rep(i,n)rep(j,g[i].size()){
      auto x=g[i][j];
      mp[{x.src,x.to}]=x.cost;
    }
    auto f1=[&](F x,F y){
      auto[a,b,c]=x;
      auto[A,B,C]=y;
      a+=A;
      b+=B;
      c+=C;
      return F(a,b,c);
    };
    auto f2=[&](F x,ll chd,ll p){
      auto[a,b,c]=x;
      mint add=mp[{chd,p}];
      c+=1;
      a+=add*b*2+add*add*c;
      b+=add*c;
      return F(a,b,c);
    };
    mint ans=0;
    Rerooting<F,decltype(g),decltype(f1),decltype(f2)> dp(g,f1,f2,F(0,0,0));
    for(auto now:dp.dp){
      ans+=get<0>(now);
    }
    ans/=2;
    cout<<ans<<endl;
    return 0;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード