Submission #66560626

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifdef INCLUDED_MAIN
int solve(){
    l1(n);
    lary(x,n);
    ll ans=-1;
    pair<ll,ll> ident = {0,0};
    
    auto f1=[&](pair<ll,ll> a, pair<ll,ll> b)->pair<ll,ll>{
        return{a.first+b.first,a.second+b.second};
    };
    auto f2 = [&](pair<ll,ll> a, pair<ll,ll> d)->pair<ll,ll>{
        ll w = d.first, base = d.second;
        return{base+a.first,a.second+w*llabs(base+a.first)};
    };
    ReRooting<pair<ll,ll>, pair<ll,ll>> rr(n,f1,f2,ident);
    rep(i,n-1){
        l3(u,v,w);
        u--;
        v--;
        rr.add_edge_bi(u,v,{w,x[v]},{w,x[u]});
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#ifdef INCLUDED_MAIN

int solve(){
    l1(n);
    lary(x,n);
    ll ans=-1;
    pair<ll,ll> ident = {0,0};
    
    auto f1=[&](pair<ll,ll> a, pair<ll,ll> b)->pair<ll,ll>{
        return{a.first+b.first,a.second+b.second};
    };
    auto f2 = [&](pair<ll,ll> a, pair<ll,ll> d)->pair<ll,ll>{
        ll w = d.first, base = d.second;
        return{base+a.first,a.second+w*llabs(base+a.first)};
    };
    ReRooting<pair<ll,ll>, pair<ll,ll>> rr(n,f1,f2,ident);
    rep(i,n-1){
        l3(u,v,w);
        u--;
        v--;
        rr.add_edge_bi(u,v,{w,x[v]},{w,x[u]});
    }
    vector<pair<ll,ll>> dp = rr.solve();
    rep(i,n){
        pair<ll,ll> cand={x[i]+dp[i].first,dp[i].second};
        if(cand.first==0){ans=cand.second;break;}
    }
    cp(ans);
    return 0;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}


#else


/*
============================================================================
                         Template for Atcoder
============================================================================

thank you.
https://ei1333.github.io/library/


*** You are FREE to use this code. ****
*** However, use at YOUR OWN RISK. ****



#ifdef INCLUDED_MAIN

int main()
{
    // main function, solve function
}

#else

    // Template code
    // .........

#define INCLUDED_MAIN
#include FILE

#endif


'''
By writting it this way, I include my self(the template) and place it below
main function.
However, please note that this currently only works on AtCoder
-it may not work on platforms like Codeforces.
'''

*/

#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <algorithm>
#include <functional>
#include <cmath>
#include <numeric>
#include <limits>
#include <iterator>
#include <cassert>
#include <stack>
#include <queue>
#include <deque>
#include <random>
#include <sstream>
#include <chrono>
#include <stdexcept>
#include <set>
#include <map>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;

/*****************  Macros  *************************************************/
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(n) for (int i = 0; i < (n); ++i)
#define rep3(i, a, b) for (int i = a; i <= (b); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; i--)
#define rrep1(n) for(int i = (n)-1; i >= 0; i--)
#define rrep3(i,a,b) for(int i = (b)-1; i >= (a); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define ssort(v) sort(all(v))
#define lsort(v) sort(all(v), greater<>())
#define pb push_back
#define eb emplace_back
#define str string
#define cp(a) cout << (a) << endl
#define yes(cond) cout << ((cond) ? "Yes" : "No") << endl
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define Yes cout << "Yes\n"
#define No cout << "No\n"
#define l1(var) ll var; cin >> var
#define l2(a,b) ll a,b; cin >> a >> b
#define l3(a,b,c) ll a,b,c; cin >> a >> b >> c
#define l4(a,b,c,d) ll a,b,c,d; cin >> a >> b >> c >> d
#define l5(a,b,c,d,e) ll a,b,c,d,e; cin >> a >> b >> c >> d >> e
#define st1(var) string var; cin >> var
#define st2(a,b) string a,b; cin >> a >> b
#define st3(a,b,c) string a,b,c; cin >> a >> b >> c
#define st4(a,b,c,d) string a,b,c,d; cin >> a >> b >> c >> d
#define st5(a,b,c,d,e) string a,b,c,d,e; cin >> a >> b >> c >> d >> e
#define lary(a, x) vector<long long> a(x); for (int i = 0; i < (x); ++i) cin >> a[i];
#define iary(a, x) vector<int> a(x); for (int i = 0; i < (x); ++i) cin >> a[i];
#define sary(a, x) vector<string> a(x); for (int i = 0; i < (x); ++i) cin >> a[i];
#define l2ary(a, r, c) vector<vector<ll>> a(r, vector<ll>(c)); \
                         for (int i=0; i<(r); ++i) for (int j=0; j<(c); ++j) cin >> a[i][j];
#define i2ary(a, r, c) vector<vector<int>> a(r, vector<int>(c)); \
                         for (int i=0; i<(r); ++i) for (int j=0; j<(c); ++j) cin >> a[i][j];

// template<class T> bool chmax(T &a, const T &b){if(a < b){a = b; return 1; } return 0;}
// template<class T> bool chmin(T &a, const T &b){if(a > b){a = b; return 1; } return 0;}



/*****************  i128  *************************************************/
// using i128 = _int128;
// constexpr i128 to_integer(const string&s) {
//     i128 = 0;
//     for (auto c:s) {
//         if (isdigit(c)) res=res * 10 + ( c - '0');
//     }
//     if (s[0] == '-') res*= -1;
//     return res;
// }
// istream& operator >> (istream &is, i128 &x) {
//     string s;
//     is >> s;
//     x = to_integer(s);
//     return is;
// }
// ostream& operator << (ostream &os, const i128 &x) {
//     int 128 ax = (x >= 0 ? x : -x);
//     char buffer[128];
//     char *d = end(buffer);
//     do {
//         --d;
//         *d = "0123456789"[ax % 10];
//         ax /= 10;
//     } while (ax != 0);
//     if( x < = 0) {
//         --d;
//         *d = '-';
//     }
//     int len = end(buffer) - d;
//     if (os.rdbuf() -> sputn(d, len) != len) {
//         os.setstate(ios_base::badbint);
//     }
//     return os;
// }

// graph
template <typename T = int>
struct Edge {
  int from, to;
  T cost;
  int idx;

  Edge() = default;

  Edge(int from, int to, T cost = 1, int idx = -1)
      : from(from), to(to), cost(cost), idx(idx) {}

  operator int() const { return to; }
};

template <typename T = int>
struct Graph {
  vector<vector<Edge<T> > > g;
  int es;

  Graph() = default;

  explicit Graph(int n) : g(n), es(0) {}

  size_t size() const { return g.size(); }

  void add_directed_edge(int from, int to, T cost = 1) {
    g[from].emplace_back(from, to, cost, es++);
  }

  void add_edge(int from, int to, T cost = 1) {
    g[from].emplace_back(from, to, cost, es);
    g[to].emplace_back(to, from, cost, es++);
  }

  void read(int M, int padding = -1, bool weighted = false,
            bool directed = false) {
    for (int i = 0; i < M; i++) {
      int a, b;
      cin >> a >> b;
      a += padding;
      b += padding;
      T c = T(1);
      if (weighted) cin >> c;
      if (directed)
        add_directed_edge(a, b, c);
      else
        add_edge(a, b, c);
    }
  }

  inline vector<Edge<T> > &operator[](const int &k) { return g[k]; }

  inline const vector<Edge<T> > &operator[](const int &k) const { return g[k]; }
};

template <typename T = int>
using Edges = vector<Edge<T> >;
// seg

template <typename S2, typename Op, typename E>
struct LambdaMonoid {
  using S = S2;
  S op(const S &a, const S &b) const { return _op(a, b); }

  S e() const { return _e(); }

  LambdaMonoid(Op _op, E _e) : _op(_op), _e(_e) {}

 private:
  Op _op;

  E _e;
};

template <typename Op, typename E>
LambdaMonoid(Op _op, E _e) -> LambdaMonoid<decltype(_e()), Op, E>;

/*
struct Monoid {
  using S = ?;
  static constexpr S op(const S& a, const S& b) {}
  static constexpr S e() {}
};
*/

template <typename Monoid>
struct SegmentTree {
  using S = typename Monoid::S;

 private:
  int n, sz;

  vector<S> seg;

  Monoid m;

 public:
  SegmentTree() = default;

  explicit SegmentTree(Monoid m, int n) : m(m), n(n) {
    sz = 1;
    while (sz < n) sz <<= 1;
    seg.assign(2 * sz, m.e());
  }

  explicit SegmentTree(Monoid m, const vector<S> &v)
      : SegmentTree(m, (int)v.size()) {
    build(v);
  }

  void build(const vector<S> &v) {
    assert(n == (int)v.size());
    for (int k = 0; k < n; k++) seg[k + sz] = v[k];
    for (int k = sz - 1; k > 0; k--) {
      seg[k] = m.op(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  void set(int k, const S &x) {
    k += sz;
    seg[k] = x;
    while (k >>= 1) {
      seg[k] = m.op(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  S get(int k) const { return seg[k + sz]; }

  S operator[](int k) const { return get(k); }

  void apply(int k, const S &x) {
    k += sz;
    seg[k] = m.op(seg[k], x);
    while (k >>= 1) {
      seg[k] = m.op(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  S prod(int l, int r) const {
    if (l >= r) return m.e();
    S L = m.e(), R = m.e();
    for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
      if (l & 1) L = m.op(L, seg[l++]);
      if (r & 1) R = m.op(seg[--r], R);
    }
    return m.op(L, R);
  }

  S all_prod() const { return seg[1]; }

  template <typename C>
  int find_first(int l, const C &check) const {
    if (l >= n) return n;
    l += sz;
    S sum = m.e();
    do {
      while ((l & 1) == 0) l >>= 1;
      if (check(m.op(sum, seg[l]))) {
        while (l < sz) {
          l <<= 1;
          auto nxt = m.op(sum, seg[l]);
          if (not check(nxt)) {
            sum = nxt;
            l++;
          }
        }
        return l + 1 - sz;
      }
      sum = m.op(sum, seg[l++]);
    } while ((l & -l) != l);
    return n;
  }

  template <typename C>
  int find_last(int r, const C &check) const {
    if (r <= 0) return -1;
    r += sz;
    S sum = m.e();
    do {
      r--;
      while (r > 1 and (r & 1)) r >>= 1;
      if (check(m.op(seg[r], sum))) {
        while (r < sz) {
          r = (r << 1) + 1;
          auto nxt = m.op(seg[r], sum);
          if (not check(nxt)) {
            sum = nxt;
            r--;
          }
        }
        return r - sz;
      }
      sum = m.op(seg[r], sum);
    } while ((r & -r) != r);
    return -1;
  }
};


struct UnionFind {
  vector<int> data;

  UnionFind() = default;

  explicit UnionFind(size_t sz) : data(sz, -1) {}

  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return true;
  }

  int find(int k) {
    if (data[k] < 0) return (k);
    return data[k] = find(data[k]);
  }

  int size(int k) { return -data[find(k)]; }

  bool same(int x, int y) { return find(x) == find(y); }

  vector<vector<int> > groups() {
    int n = (int)data.size();
    vector<vector<int> > ret(n);
    for (int i = 0; i < n; i++) {
      ret[find(i)].emplace_back(i);
    }
    ret.erase(remove_if(begin(ret), end(ret),
                        [&](const vector<int> &v) { return v.empty(); }),
              end(ret));
    return ret;
  }
};
/*****************  Debug  *************************************************/
#ifdef LOCAL

#define debug(x) cerr << #x << ": " << (x) << endl;
#else
#define debug(x)
#endif

#ifdef LOCAL
template<typename T> void debug_vector(const vector<T>& v) {
    cerr << "[ ";
    for (const auto& x : v) cerr << x << " ";
    cerr << "]" << endl;
}
template<typename T, typename U> void debug_map(const map<T, U>& m) {
    cerr << "{ ";
    for (const auto& [key, val] : m) cerr << key << ": " << val << ", ";
    cerr << "}" << endl;
}
#define debug2d(v) for (const auto& row : (v)) debug_vector(row)
#endif
// }


const int INF = 1e9 + 5;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

/*********** Library Pasting Area   *****************************************/
template< typename Data, typename T >
struct ReRooting {
 
  struct Node {
    int to, rev;
    Data data;
  };
 
  using F1 = function< T(T, T) >;
  using F2 = function< T(T, Data) >;
 
  vector< vector< Node > > g;
  vector< vector< T > > ldp, rdp;
  vector< int > lptr, rptr;
  const F1 f1;
  const F2 f2;
  const T ident;
 
  ReRooting(int n, const F1 &f1, const F2 &f2, const T &ident) :
      g(n), ldp(n), rdp(n), lptr(n), rptr(n), f1(f1), f2(f2), ident(ident) {}
 
  void add_edge(int u, int v, const Data &d) {
    g[u].emplace_back((Node) {v, (int) g[v].size(), d});
    g[v].emplace_back((Node) {u, (int) g[u].size() - 1, d});
  }
 
  void add_edge_bi(int u, int v, const Data &d, const Data &e) {
    g[u].emplace_back((Node) {v, (int) g[v].size(), d});
    g[v].emplace_back((Node) {u, (int) g[u].size() - 1, e});
  }
 
 
  T dfs(int idx, int par) {
 
    while(lptr[idx] != par && lptr[idx] < g[idx].size()) {
      auto &e = g[idx][lptr[idx]];
      ldp[idx][lptr[idx] + 1] = f1(ldp[idx][lptr[idx]], f2(dfs(e.to, e.rev), e.data));
      ++lptr[idx];
    }
    while(rptr[idx] != par && rptr[idx] >= 0) {
      auto &e = g[idx][rptr[idx]];
      rdp[idx][rptr[idx]] = f1(rdp[idx][rptr[idx] + 1], f2(dfs(e.to, e.rev), e.data));
      --rptr[idx];
    }
    if(par < 0) return rdp[idx][0];
    return f1(ldp[idx][par], rdp[idx][par + 1]);
  }
 
  vector< T > solve() {
    for(int i = 0; i < g.size(); i++) {
      ldp[i].assign(g[i].size() + 1, ident);
      rdp[i].assign(g[i].size() + 1, ident);
      lptr[i] = 0;
      rptr[i] = (int) g[i].size() - 1;
    }
    vector< T > ret;
    for(int i = 0; i < g.size(); i++) {
      ret.push_back(dfs(i, -1));
    }
    return ret;
  }
};

/**********************************************************************/

#define INCLUDED_MAIN
#include __FILE__
#endif

Submission Info

Compile Error

Main.cpp: In instantiation of ‘std::vector<_ValT> ReRooting<Data, T>::solve() [with Data = std::pair<long long int, long long int>; T = std::pair<long long int, long long int>]’:
Main.cpp:23:38:   required from here
Main.cpp:510:22: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::vector<ReRooting<std::pair<long long int, long long int>, std::pair<long long int, long long int> >::Node, std::allocator<ReRooting<std::pair<long long int, long long int>, std::pair<long long int, long long int> >::Node> >, std::allocator<std::vector<ReRooting<std::pair<long long int, long long int>, std::pair<long long int, long long int> >::Node, std::allocator<ReRooting<std::pair<long long int, long long int>, std::pair<long long int, long long int> >::Node> > > >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  510 |     for(int i = 0; i < g.size(); i++) {
      |                    ~~^~~~~~~~~~
Main.cpp:517:22: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::vector<ReRooting<std::pair<long long int, long long int>, std::pair<long long int, long long int> >::Node, std::allocator<ReRooting<std::pair<long long int, long long int>, std::pair<long long int, long long int> >::Node> >, std::allocator<std::vector<ReRooting<std::pair<long long int, long long int>, std::pair<long long int, long long int> >::Node, std::allocator<ReRooting<std::pair<long long int, long long int>, std::pair<long long int, long long int> >::Node> > > >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  517 |     for(int i = 0; i < g.size(); i++) {
      |                    ~~^~~~~~~~~~
Main.cpp: In instantiation of ‘T ReRooting<Data, T>::dfs(int, int) [with Data = std::pair<long long int, long long int>; T = std::pair<long long int, long long int>]’:
Main.cpp:518:21:   required from ‘std::vector<_ValT> ReRooting<Data, T>::solve() [with Data = std::pair<long long int, long long int>; T = std::pair<long long int, long long int>]’
Main.cpp:23:38:   required from here
Main.cpp:495:41: warning: comparison of integer expressions of different signedness: ‘__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type’ {aka ‘int’} and ‘std::vector<ReRooting<std::pair<long long int, long long int>, std::pair<long long int, long long int> >::Node, std::allocator<ReRooting<std::pair<long long int, long long int>, std::pair<long long int, long long int> >::Node> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  495 |     while(lptr[idx] != par && lptr[idx] < g[idx].size()) {

Judge Result