oj.uz

Submission #357580

# Submission time Handle Problem Language Result Execution time Memory
357580 2021-01-24T07:40:30 Z Thistle Election Campaign (JOI15_election_campaign) C++14
100 / 100
 802 ms 61036 KB 
#pragma GCC target ("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
#include<complex>
#include<time.h>
#include<cassert>
#include<functional>
#include<numeric>
#include<tuple>
using namespace std;
using ll = long long;
using ld = long double;
using H = pair<ll, ll>;
using P = pair<ll, H>;
using vi = vector<ll>;
#define all(a) (a).begin(),(a).end()
#define fs first
#define sc second
#define xx first
#define yy second.first
#define zz second.second
#define Q(i,j,k) mkp(i,mkp(j,k))
#define rng(i,s,n) for(ll i = (s) ; i < (n) ; i++)
#define rep(i,n) rng(i, 0, (n))
#define mkp make_pair
#define vec vector
#define pb emplace_back
#define siz(a) int(a.size())
#define crdcomp(b) sort(all((b)));(b).erase(unique(all((b))),(b).end())
#define getidx(b,i) (lower_bound(all(b),(i))-(b).begin())
#define ssp(i,n) (i==(ll)(n)-1?"\n":" ")
#define ctoi(c) (int)(c-'0')
#define itoc(c) (char)(c+'0')
#define cyes printf("Yes\n")
#define cno printf("No\n")
#define cdf(n) for(int quetimes_=(n);quetimes_>0;quetimes_--)
#define gcj printf("Case #%lld: ",qq123_+1)
#define readv(a,n) a.resize(n,0);rep(i,(n)) a[i]=read()
#define found(a,x) (a.find(x)!=a.end())
constexpr ll mod = (ll)1e9 + 7;
constexpr ll Mod = 998244353;
constexpr ld EPS = 1e-10;
constexpr ll inf = (ll)3 * 1e18;
constexpr int Inf = (ll)15 * 1e8;
constexpr int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 };
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 (b < a) { a = b; return 1; } return 0; }
ll read() { ll u, k = scanf("%lld", &u); return u; }
string reads() { string s; cin >> s; return s; }
H readh(short g = 0) { H u; int k = scanf("%lld %lld", &u.fs, &u.sc); if (g == 1) u.fs--, u.sc--; if (g == 2) u.fs--; return u; }
bool ina(H t, int h, int w) { return 0 <= t.fs && t.fs < h && 0 <= t.sc && t.sc < w; }
bool ina(int t, int l, int r) { return l <= t && t < r; }
ll gcd(ll i, ll j) { return j ? gcd(j, i % j) : i; }
ll ppc(ll x) {
    int sum = 0; for (int i = 0; i < 60; i++)if ((1ll << i) & x) sum++;
    return sum;
}
template<typename T>
void fin(T x) { cout << x << endl; exit(0); }

template<typename T>
class csum {
    vec<T> v;
public:
    csum(vec<T>& a) :v(a) { build(); }
    csum() {}
    csum(int sz) { init(sz); }
    void init(int sz) { v = vector<T>(sz + 1, 0); }
    void init(vec<T>& a) { v = a; build(); }
    void build() {
        for (int i = 1; i < v.size(); i++) v[i] += v[i - 1];
    }
    void add(int l, int r, T x) {
        v[l] += x;
        v[r] -= x;
    }//[l,r)
    void add(int t, T x) {
        v[t] += x;
    }//[l,r)
    //[l,r]
    T a(int l, int r) {
        if (r < l) return 0;
        return v[r] - (l == 0 ? 0 : v[l - 1]);
    }
    //[l,r)
    T b(int l, int r) {
        return a(l, r - 1);
    }
    T a(pair<int, int>t) {
        return a(t.first, t.second);
    }
    T b(pair<int, int>t) {
        return b(t.first, t.second);
    }
    T operator[](int x)const {
        return v[x];
    }
};
template<ll mod>
class modint {
public:ll v;
      modint(ll v = 0) { s(v % mod + mod); }
      constexpr static int fn_ = (ll)2e6 + 5;
      static vector<modint>fact, comp;
      modint pow(ll x) const {
          modint b(v), c(1);
          while (x) {
              if (x & 1) c *= b;
              b *= b;
              x >>= 1;
          }
          return c;
      }
      inline modint& s(int vv) {
          v = vv < mod ? vv : vv - mod;
          return *this;
      }
      inline modint inv()const { return pow(mod - 2); }
      inline modint operator-()const { return modint() - *this; }
      inline modint& operator+=(const modint b) { return s(v + b.v); }
      inline modint& operator-=(const modint b) { return s(v + mod - b.v); }
      inline modint& operator*=(const modint b) { v = v * b.v % mod; return *this; }
      inline modint& operator/=(const modint b) { v = v * b.inv().v % mod; return *this; }
      inline modint operator+(const modint& b) const { return modint(v) += b; }
      inline modint operator-(const modint& b) const { return modint(v) -= b; }
      inline modint operator*(const modint& b) const { return modint(v) *= b; }
      inline modint operator/(const modint& b) const { return modint(v) /= b; }
      friend ostream& operator<<(ostream& os, const modint& m) {
          return os << m.v;
      }
      friend istream& operator>>(istream& is, modint& m) {
          int x; is >> x; m = modint(x);
          return is;
      }
      bool operator<(const modint& r)const { return v < r.v; }
      bool operator>(const modint& r)const { return v > r.v; }
      bool operator<=(const modint& r)const { return v <= r.v; }
      bool operator>=(const modint& r)const { return v >= r.v; }
      bool operator==(const modint& r)const { return v == r.v; }
      bool operator!=(const modint& r)const { return v != r.v; }
      explicit operator bool()const { return v; }
      explicit operator int()const { return v; }
      modint comb(modint k) {
          if (k > *this) return modint();
          if (fact.empty()) combinit();
          if (v >= fn_) {
              if (k > *this - k) k = *this - k;
              modint tmp(1);
              for (int i = v; i >= v - k.v + 1; i--) tmp *= modint(i);
              return tmp * comp[k.v];
          }
          return fact[v] * comp[k.v] * comp[v - k.v];
      }//nCk
      modint perm(modint k) {
          if (k > *this) return modint();
          if (fact.empty()) combinit();
          if (v >= fn_) {
              modint tmp(1);
              for (int i = v; i >= v - k.v + 1; i--) tmp *= modint(i);
              return tmp;
          }
          return fact[v] * comp[v - k.v];
      }//nPk
      static void combinit() {
          fact.assign(fn_, modint());
          fact[0] = 1;
          for (int i = 1; i < fn_; i++) fact[i] = fact[i - 1] * modint(i);
          comp.assign(fn_, modint());
          comp[fn_ - 1] = fact[fn_ - 1].inv();
          for (int i = fn_ - 2; i >= 0; i--) comp[i] = comp[i + 1] * modint(i + 1);
      }
};
using mint = modint<ll(1e9 + 7)>; template<>vec<mint> mint::fact = vec<mint>(); template<>vec<mint> mint::comp = vec<mint>();
//--------------------------------------------------------------
//--------------------------------------------------------------
class Segtree {
    int n, rr;
    vi dat;
public:
    Segtree() {}
    void init(int m) {
        n = m;
        rr = 1; while (rr < n) rr *= 2;
        dat.assign(2 * rr, 0);
    }
    void add(int t, ll x) {
        t += rr;
        dat[t] += x;
        while (t > 0) {
            t /= 2;
            dat[t] = dat[t * 2] + dat[t * 2 + 1];
        }
    }
    ll query(int l, int r) {
        return query(1, l, r, 0, rr);
    }
private:
    ll query(int i, int a, int b, int l, int r) {
        if (b <= l || r <= a) return 0;
        if (a <= l && r <= b) return dat[i];
        return query(i * 2, a, b, l, (l + r) / 2) + query(i * 2 + 1, a, b, (l + r) / 2, r);
    }
};
vec<int> e[200000];
class HLD {
    int n;
    Segtree seg;
public:
    vi dpt, pa, in, sz, head;
    HLD(int n) :n(n) {
        dpt.assign(n, -1);
        pa.assign(n, -1);
        in.assign(n, -1);
        sz.assign(n, 1);
        head.assign(n, 0);
        dfs1(0, -1, 0);
        int idx = 0;
        dfs2(0, -1, idx);
        seg.init(idx);
    }
    void add(int x, ll t) {
        seg.add(in[x], t);
    }
    ll query(int a, int b) {
        ll sum = 0;
        while (head[a] != head[b]) {
            if (in[a] < in[b]) swap(a, b);
            sum += seg.query(in[head[a]], in[a] + 1);
            a = pa[head[a]];
        }
        if (in[a] > in[b]) swap(a, b);
        sum += seg.query(in[a], in[b] + 1);
        return sum;
    }
    int lca(int a, int b) {
        while (head[a] != head[b]) {
            if (in[a] < in[b]) swap(a, b);
            a = pa[head[a]];
        }
        if (in[a] > in[b]) swap(a, b);
        return a;
    }
private:
    void dfs1(int x, int p, int d) {
        dpt[x] = d;
        pa[x] = p;
        if (e[x][0] == p) swap(e[x][0], e[x].back());
        for (auto& g : e[x]) {
            if (g == p) continue;
            dfs1(g, x, d + 1);
            sz[x] += sz[g];
            if (sz[g] > sz[e[x][0]]) {
                swap(g, e[x][0]);
            }
        }
    }
    void dfs2(int x, int p, int& idx) {
        in[x] = idx++;
        for (auto g : e[x]) {
            if (g == p) continue;
            head[g] = (g == e[x][0] ? head[x] : g);
            dfs2(g, x, idx);
        }
    }
};
vec<P> qry[200000];
signed main() {
    int n, m; cin >> n;
    rep(i, n - 1) {
        int u, v; cin >> u >> v;
        u--; v--;
        e[u].pb(v); e[v].pb(u);
    }
    HLD hld(n), hld2(n);
    cin >> m;
    rep(i, m) {
        int a, b; ll x; cin >> a >> b >> x;
        a--; b--;
        qry[hld.lca(a, b)].pb(Q(a, b, x));
    }
    auto dfs = [&](int x, int p, auto& dfs)->ll {
        ll val = 0;
        vi u, v, k;
        for (auto g : e[x]) {
            if (g == p) continue;
            v.pb(dfs(g, x, dfs));
            val += v.back();
            k.pb(g);
            u.pb(hld.in[g]);
        }
        ll ret = val;
        for (auto g : qry[x]) {
            int a = g.xx, b = g.yy; ll c = g.zz;
            if (b == x) swap(a, b);
            int pp = k[upper_bound(all(u), hld.in[b]) - u.begin() - 1];
            ll r = c + hld2.query(b, pp) - hld.query(b, pp);
            r += val;
            if (a != x) {
                int pa = k[upper_bound(all(u), hld.in[a]) - u.begin() - 1];
                r += hld2.query(a, pa) - hld.query(a, pa);
            }
            chmax(ret, r);
        }
        hld.add(x, ret);
        if (x) hld2.add(hld.pa[x], ret);
        return ret;
    };
    cout << dfs(0, -1, dfs) << endl;
}

Compilation message

election_campaign.cpp: In function 'll read()':
election_campaign.cpp:69:19: warning: unused variable 'k' [-Wunused-variable]
   69 | ll read() { ll u, k = scanf("%lld", &u); return u; }
      |                   ^
election_campaign.cpp: In function 'H readh(short int)':
election_campaign.cpp:71:33: warning: unused variable 'k' [-Wunused-variable]
   71 | H readh(short g = 0) { H u; int k = scanf("%lld %lld", &u.fs, &u.sc); if (g == 1) u.fs--, u.sc--; if (g == 2) u.fs--; return u; }
      |                                 ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 7 ms 9708 KB Output is correct
3 Correct 7 ms 9708 KB Output is correct
4 Correct 8 ms 9836 KB Output is correct
5 Correct 219 ms 26216 KB Output is correct
6 Correct 140 ms 55660 KB Output is correct
7 Correct 176 ms 45420 KB Output is correct
8 Correct 163 ms 26960 KB Output is correct
9 Correct 191 ms 39660 KB Output is correct
10 Correct 166 ms 27016 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9708 KB Output is correct
2 Correct 7 ms 9708 KB Output is correct
3 Correct 9 ms 10220 KB Output is correct
4 Correct 298 ms 60652 KB Output is correct
5 Correct 304 ms 60652 KB Output is correct
6 Correct 290 ms 60524 KB Output is correct
7 Correct 310 ms 60724 KB Output is correct
8 Correct 294 ms 60652 KB Output is correct
9 Correct 274 ms 60652 KB Output is correct
10 Correct 296 ms 60524 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9708 KB Output is correct
2 Correct 7 ms 9708 KB Output is correct
3 Correct 9 ms 10220 KB Output is correct
4 Correct 298 ms 60652 KB Output is correct
5 Correct 304 ms 60652 KB Output is correct
6 Correct 290 ms 60524 KB Output is correct
7 Correct 310 ms 60724 KB Output is correct
8 Correct 294 ms 60652 KB Output is correct
9 Correct 274 ms 60652 KB Output is correct
10 Correct 296 ms 60524 KB Output is correct
11 Correct 35 ms 11420 KB Output is correct
12 Correct 314 ms 60904 KB Output is correct
13 Correct 304 ms 60908 KB Output is correct
14 Correct 293 ms 60968 KB Output is correct
15 Correct 303 ms 60908 KB Output is correct
16 Correct 295 ms 61036 KB Output is correct
17 Correct 324 ms 60888 KB Output is correct
18 Correct 309 ms 60780 KB Output is correct
19 Correct 305 ms 60980 KB Output is correct
20 Correct 304 ms 60824 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 802 ms 30440 KB Output is correct
2 Correct 274 ms 60780 KB Output is correct
3 Correct 419 ms 49320 KB Output is correct
4 Correct 423 ms 31008 KB Output is correct
5 Correct 374 ms 47148 KB Output is correct
6 Correct 436 ms 31196 KB Output is correct
7 Correct 442 ms 46500 KB Output is correct
8 Correct 510 ms 30572 KB Output is correct
9 Correct 278 ms 60524 KB Output is correct
10 Correct 438 ms 42984 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 7 ms 9708 KB Output is correct
3 Correct 7 ms 9708 KB Output is correct
4 Correct 8 ms 9836 KB Output is correct
5 Correct 219 ms 26216 KB Output is correct
6 Correct 140 ms 55660 KB Output is correct
7 Correct 176 ms 45420 KB Output is correct
8 Correct 163 ms 26960 KB Output is correct
9 Correct 191 ms 39660 KB Output is correct
10 Correct 166 ms 27016 KB Output is correct
11 Correct 10 ms 9964 KB Output is correct
12 Correct 9 ms 10220 KB Output is correct
13 Correct 9 ms 10092 KB Output is correct
14 Correct 9 ms 9964 KB Output is correct
15 Correct 10 ms 9964 KB Output is correct
16 Correct 9 ms 9964 KB Output is correct
17 Correct 9 ms 9964 KB Output is correct
18 Correct 9 ms 10092 KB Output is correct
19 Correct 9 ms 9964 KB Output is correct
20 Correct 9 ms 10220 KB Output is correct

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 7 ms 9708 KB Output is correct
3 Correct 7 ms 9708 KB Output is correct
4 Correct 8 ms 9836 KB Output is correct
5 Correct 219 ms 26216 KB Output is correct
6 Correct 140 ms 55660 KB Output is correct
7 Correct 176 ms 45420 KB Output is correct
8 Correct 163 ms 26960 KB Output is correct
9 Correct 191 ms 39660 KB Output is correct
10 Correct 166 ms 27016 KB Output is correct
11 Correct 8 ms 9708 KB Output is correct
12 Correct 7 ms 9708 KB Output is correct
13 Correct 9 ms 10220 KB Output is correct
14 Correct 298 ms 60652 KB Output is correct
15 Correct 304 ms 60652 KB Output is correct
16 Correct 290 ms 60524 KB Output is correct
17 Correct 310 ms 60724 KB Output is correct
18 Correct 294 ms 60652 KB Output is correct
19 Correct 274 ms 60652 KB Output is correct
20 Correct 296 ms 60524 KB Output is correct
21 Correct 35 ms 11420 KB Output is correct
22 Correct 314 ms 60904 KB Output is correct
23 Correct 304 ms 60908 KB Output is correct
24 Correct 293 ms 60968 KB Output is correct
25 Correct 303 ms 60908 KB Output is correct
26 Correct 295 ms 61036 KB Output is correct
27 Correct 324 ms 60888 KB Output is correct
28 Correct 309 ms 60780 KB Output is correct
29 Correct 305 ms 60980 KB Output is correct
30 Correct 304 ms 60824 KB Output is correct
31 Correct 802 ms 30440 KB Output is correct
32 Correct 274 ms 60780 KB Output is correct
33 Correct 419 ms 49320 KB Output is correct
34 Correct 423 ms 31008 KB Output is correct
35 Correct 374 ms 47148 KB Output is correct
36 Correct 436 ms 31196 KB Output is correct
37 Correct 442 ms 46500 KB Output is correct
38 Correct 510 ms 30572 KB Output is correct
39 Correct 278 ms 60524 KB Output is correct
40 Correct 438 ms 42984 KB Output is correct
41 Correct 10 ms 9964 KB Output is correct
42 Correct 9 ms 10220 KB Output is correct
43 Correct 9 ms 10092 KB Output is correct
44 Correct 9 ms 9964 KB Output is correct
45 Correct 10 ms 9964 KB Output is correct
46 Correct 9 ms 9964 KB Output is correct
47 Correct 9 ms 9964 KB Output is correct
48 Correct 9 ms 10092 KB Output is correct
49 Correct 9 ms 9964 KB Output is correct
50 Correct 9 ms 10220 KB Output is correct
51 Correct 520 ms 31064 KB Output is correct
52 Correct 310 ms 60868 KB Output is correct
53 Correct 444 ms 43680 KB Output is correct
54 Correct 372 ms 31328 KB Output is correct
55 Correct 758 ms 30868 KB Output is correct
56 Correct 311 ms 61016 KB Output is correct
57 Correct 373 ms 45736 KB Output is correct
58 Correct 421 ms 31264 KB Output is correct
59 Correct 526 ms 31116 KB Output is correct
60 Correct 302 ms 60780 KB Output is correct
61 Correct 381 ms 45992 KB Output is correct
62 Correct 445 ms 31300 KB Output is correct
63 Correct 775 ms 30848 KB Output is correct
64 Correct 311 ms 60908 KB Output is correct
65 Correct 446 ms 45984 KB Output is correct
66 Correct 380 ms 31260 KB Output is correct
67 Correct 786 ms 31196 KB Output is correct
68 Correct 304 ms 60780 KB Output is correct
69 Correct 390 ms 41384 KB Output is correct
70 Correct 426 ms 31256 KB Output is correct