oj.uz

Submission #239161

# Submission time Handle Problem Language Result Execution time Memory
239161 2020-06-14T16:09:38 Z Plasmatic Dynamic Diameter (CEOI19_diameter) C++11
49 / 100
 5000 ms 150632 KB 
#pragma GCC optimize "Ofast"
#pragma GCC optimize "unroll-loops"
#pragma GCC target "sse,sse2,sse3,sse4,abm,avx,mmx,popcnt"
#pragma region
#include "bits/stdc++.h"
using namespace std;
// Common Type shorteners and int128
using ll = long long; using ull = unsigned long long; using ld = long double;
using pii = pair<int, int>; using pll = pair<ll, ll>;
template <typename T> using vec = vector<T>;
template <typename K, typename V> using umap = unordered_map<K, V>; template <typename K> using uset = unordered_set<K>;
using vi = vec<int>; using vl = vec<ll>; using vpi = vec<pii>; using vpl = vec<pll>;
#ifdef __SIZEOF_INT128__
using int128 = __int128_t; using uint128 = __uint128_t;
#endif
template<typename I> string intStr(I x) { string ret; while (x > 0) { ret += (x % 10) + '0'; x /= 10; } reverse(ret.begin(), ret.end()); return ret; } // Int to string
// Shorthand Macros
#define INF 0x3f3f3f3f
#define LLINF 0x3f3f3f3f3f3f3f3f
#define mpr make_pair
#define mtup make_tuple
#define pb push_back
#define popcount __builtin_popcount
#define clz __builtin_clz
#define ctz __builtin_ctz
#define popcountll __builtin_popcountll
#define clzll __builtin_clzll
#define ctzll __builtin_ctzll
#define finline __attribute__((always_inline))
// Shorthand Function Macros
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (__typeof(a) i = a; i < b; i++)
#define reprev(i, a, b) for (__typeof(a) i = a; i > b; i--)
#define repi(a, b) rep(i, a, b)
#define repj(a, b) rep(j, a, b)
#define repk(a, b) rep(k, a, b)
#define Cmplt(type) bool operator<(const type &o) const
#define Cmpgt(type) bool operator>(const type &o) const
#define Cmpfn(name, type) bool name(const type &a, const type &b)
#define Inop(type) istream& operator>>(istream& in, type &o)
#define Outop(type) ostream& operator<<(ostream& out, type o)
#define Pow2(x) (1LL << (x))
#define scn(type, ...) type __VA_ARGS__; scan(__VA_ARGS__) // scn -> Short for SCan New
// Shorthand Functions
// template<typename T> inline int sz(const T &x) { return x.size(); }
template<typename T> inline void maxa(T& st, T v) { st = max(st, v); }
template<typename T> inline void mina(T& st, T v) { st = min(st, v); }
inline void setprec(ostream& out, int prec) { out << setprecision(prec) << fixed; }
// Out operators and printing for arrays and vectors
template <typename T> ostream& operator<<(ostream& out,vector<T> iter){out<<"[";for(auto t:iter){out<<t<<", ";}out<<"]";return out;}
template <typename T> string arrayStr(T *arr,int sz){string ret = "[";for(int i=0;i<sz;i++){ret+=to_string(arr[i])+", "; } return ret + "]";}
template <typename T> void printArray(T *arr,int sz){for(int i=0;i<sz;i++){cout<<arr[i]<<" "; } cout<<"\n";}
// I/O Operations
inline void scan(){}
template<typename F, typename... R> inline void scan(F &f,R&... r){cin>>f;scan(r...);}
template <typename F> inline void println(F t){cout<<t<<'\n';}
template<typename F, typename... R> inline void println(F f,R... r){cout<<f<<" ";println(r...);}
inline void print(){}
template<typename F, typename... R> inline void print(F f,R... r){cout<<f;print(r...);}
// Debugging
#define db(x) cout << (#x) << ": " << (x) << ", "
#define dblb(s) cout << "[" << (s) << "] "
#define dba(alias, x) cout << (alias) << ": " << (x) << ", "
template<typename F> inline string __generic_tostring(F f) { stringstream ss; ss << f; return ss.str(); }
template<typename F> inline string __join_comma(F f) {return __generic_tostring(f);}
template<typename F, typename... R> string __join_comma(F f, R... r) { return __generic_tostring(f) + ", " + __join_comma(r...); }
#define dbp(alias, ...) cout << (alias) << ": (" << __join_comma(__VA_ARGS__) << "), "
#define dbbin(x, n) cout << (#x) << ": " << bitset<n>(x) << ", "
#define dbarr(x, n) cout << (#x) << ": " << arrayStr((x), (n)) << ", "
#define dbln cout << endl;
#pragma endregion

const int MN = 1e5 + 1, LG = 18;
int N, Q,
    A[MN], B[MN], lv[MN];
ll W, 
    weight[MN];
struct Ed {
    int i, v;
    ll w() { return weight[i]; }
};
vec<Ed> g[MN];

int sz[MN];
bool block[MN];

int gsz(int c, int p) {
    sz[c] = 1;
    for (auto to : g[c])
        if (to.v != p && !block[to.v])
            sz[c] += gsz(to.v, c);
    return sz[c];
}
int gcent(int c, int p, int req) {
    for (auto to : g[c])
        if (to.v != p && !block[to.v] && sz[to.v] > req)
            return gcent(to.v, c, req);
    return c;
}

// Bottom up segment tree supporting range updates and range queries
// Indices are 0-indexed and ranges are inclusive
// In practice, has a small constant, not quite as fast as fenwick trees,
//   and similar performance as top down segment trees
// A combine struct is provided with typedefs/using for data and lazy,
//   a query default value (qdef), lazy default value (ldef),
//   and implementations of merge, applyLazy, getSegmentVal, and mergeLazy
// Below is a sample struct for range assignment and range sum queries
struct Combine {
  using Data = ll;
  using Lazy = ll;
  const Data qdef = -LLINF;
  const Lazy ldef = 0;
  Data merge(const Data &l, const Data &r) const { return max(l, r); }
  Data applyLazy(const Data &l, const Lazy &r) const { return l + r; }
  Lazy getSegmentVal(const Lazy &v, int k) const { return v; }
  Lazy mergeLazy(const Lazy &l, const Lazy &r) const { return l + r; }
};
// Time Complexity:
//   constructor: O(N)
//   update, query: O(log N)
// Memory Complexity: O(N)
// Tested:
//   https://dmoj.ca/problem/dmopc17c4p6
//   https://dmoj.ca/problem/dmopc18c5p5
//   https://dmoj.ca/problem/dmopc18c6p5
//   https://dmoj.ca/problem/lazy
//   https://mcpt.ca/problem/seq3
template <class Combine> struct SegmentTreeLazyBottomUp {
  using Data = typename Combine::Data; using Lazy = typename Combine::Lazy;
  Combine C; int N, lgN; vector<Data> TR; vector<Lazy> LZ;
  void apply(int i, const Lazy &v, int k) {
    TR[i] = C.applyLazy(TR[i], C.getSegmentVal(v, k));
    if (i < N) LZ[i] = C.mergeLazy(LZ[i], v);
  }
  void pushup(int i) {
    for (int k = 2; i /= 2; k *= 2) {
      TR[i] = C.merge(TR[i * 2], TR[i * 2 + 1]);
      if (LZ[i] != C.ldef)
        TR[i] = C.applyLazy(TR[i], C.getSegmentVal(LZ[i], k));
    }
  }
  void propagate(int i) {
    int h = lgN + 1, k = 1 << lgN, ii = i >> h;
    for (; h > 0; ii = i >> --h, k /= 2) if (LZ[ii] != C.ldef) {
      apply(ii * 2, LZ[ii], k); apply(ii * 2 + 1, LZ[ii], k); LZ[ii] = C.ldef;
    }
  }
  void init(int n0, const Data vdef) {
      N = n0;
      lgN = __lg(N);
      TR = vector<Data>(N * 2, C.qdef);
      LZ = vector<Data>(N, C.ldef); 
      fill(TR.begin() + N, TR.end(), vdef);
      for (int i = N - 1; i > 0; i--) TR[i] = C.merge(TR[i * 2], TR[i * 2 + 1]);
  }
  void update(int l, int r, const Lazy &v) {
    int l0 = l += N, r0 = r += N, k = 1; propagate(l); propagate(r);
    for (; l <= r; l /= 2, r /= 2, k *= 2) {
      if (l & 1) apply(l++, v, k);
      if (!(r & 1)) apply(r--, v, k);
    }
    pushup(l0); pushup(r0);
  }
  Data query(int l, int r) {
    propagate(l += N); propagate(r += N); Data ql = C.qdef, qr = C.qdef;
    for (; l <= r; l /= 2, r /= 2) {
      if (l & 1) ql = C.merge(ql, TR[l++]);
      if (!(r & 1)) qr = C.merge(TR[r--], qr);
    }
    return C.merge(ql, qr);
  }
};

int fst[LG][MN], lst[LG][MN];
struct DS {
    int n, lg;
    vi tour;
    vector<pair<int, ll>> dis;
    SegmentTreeLazyBottomUp<Combine> seg;
    void dfs(int c, int p, ll cdis) {
        tour.pb(c);
        fst[lg][c] = tour.size() - 1;
        dis.emplace_back(c, cdis);
        for (auto to : g[c]) {
            if (to.v != p && !block[to.v]) {
                dfs(to.v, c, cdis + to.w());
            }
        }
        lst[lg][c] = tour.size() - 1;
    }
    void init(int c, int lg0) {
        // dfs and init tour
        // dblb("init"); db(c); db(pre); dbln;
        lg = lg0;
        dfs(c, -1, 0);
        // init seg
        n = tour.size();
        seg.init(n, -LLINF);
        sort(all(dis));
        for (auto p : dis) {
            int id = fst[lg][p.first];
            seg.update(id, id, LLINF + p.second); // to counteract the infinity (TM)
        }
    }
    ll get(int node) {
        return seg.query(fst[lg][node], lst[lg][node]);
    }
    int getBottomNode(int a, int b) {
        ll da = lower_bound(all(dis), mpr(a, -1LL))->second, db = lower_bound(all(dis), mpr(b, -1LL))->second;
        return da > db ? a : b;
    }
    void inc(int root, ll amt) {
        seg.update(fst[lg][root], lst[lg][root], amt);
    }
};
multiset<ll, greater<ll>> allDist, centDist[MN];
ll preAllDist[MN];
DS paths[MN];
int chForEdge[LG][MN];
vi hasEdge[MN]; // centroids that have that edge

void setupEdge(int c, int p, int cent, int chid) {
    for (auto to : g[c]) {
        if (to.v != p && !block[to.v]) {
            hasEdge[to.i].pb(cent);
            chForEdge[lv[cent]][to.i] = chid;
            setupEdge(to.v, c, cent, chid);
        }
    }
}

ll getDia(multiset<ll, greater<ll>> &ms) {
    if (int(ms.size()) >= 2)
        return *ms.begin() + *(++ms.begin());
    return *ms.begin();
}

void decomp(int c, int clv) {
    gsz(c, -1);
    if (sz[c] == 1) return;
    int cent = gcent(c, -1, sz[c] / 2);
    lv[cent] = clv;

    paths[cent].init(cent, clv);
    repi(0, int(g[cent].size())) {
        auto to = g[cent][i];
        if (!block[to.v]) {
            centDist[cent].insert(paths[cent].get(to.v));

            setupEdge(to.v, cent, cent, i);
            hasEdge[to.i].pb(cent);
            chForEdge[clv][to.i] = i;
        }
    }

    ll dia = getDia(centDist[cent]);
    allDist.insert(dia);
    // dblb("initial"); db(cent); db(sz[c]); db(dia); dbln;
    preAllDist[cent] = dia;

    block[cent] = true;
    for (auto to : g[cent]) {
        if (!block[to.v])
            decomp(to.v, clv + 1);
    }
}

void pm(multiset<ll, greater<ll>> &s) {
    for (auto p : s)
        print(p, ' ');
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    scan(N, Q, W);
    repi(0, N - 1) {
        scn(int, a, b);
        scn(ll, w);
        g[a].pb({i, b});
        g[b].pb({i, a});
        weight[i] = w;
        A[i] = a;
        B[i] = b;
    }

    decomp(1, 0);

    ll lastAns = 0;
    while (Q--) {
        scn(ll, e, w);
        e = (e + lastAns) % (N - 1);
        w = (w + lastAns) % W;
        
        ll dif = w - weight[e];
        for (int cent : hasEdge[e]) {
            int chid = chForEdge[lv[cent]][e], to = g[cent][chid].v;
            auto &ps = paths[cent];

            // rem old
            ll old = ps.get(to);
            // dblb("upd"); db(e); db(w); db(dif); db(cent); db(chid); db(ps.get()); db(old); db(preAllDist[cent]); dbln;
            // pm(centDist[cent]); dbln;
            // pm(allDist); dbln;
            centDist[cent].erase(centDist[cent].find(old));
            allDist.erase(allDist.find(preAllDist[cent]));

            // ins new
            int bot = ps.getBottomNode(A[e], B[e]);
            ps.inc(bot, dif);
            centDist[cent].insert(ps.get(to));
            preAllDist[cent] = getDia(centDist[cent]);
            allDist.insert(preAllDist[cent]);
        }
        weight[e] = w;

        lastAns = *allDist.begin();
        println(lastAns);
    }

    return 0;
}

Compilation message

diameter.cpp:4:0: warning: ignoring #pragma region  [-Wunknown-pragmas]
 #pragma region
 
diameter.cpp:71:0: warning: ignoring #pragma endregion  [-Wunknown-pragmas]
 #pragma endregion

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 22400 KB Output is correct
2 Correct 17 ms 22400 KB Output is correct
3 Correct 17 ms 22400 KB Output is correct
4 Correct 17 ms 22400 KB Output is correct
5 Correct 17 ms 22400 KB Output is correct
6 Correct 18 ms 22400 KB Output is correct
7 Correct 18 ms 22272 KB Output is correct
8 Correct 18 ms 22400 KB Output is correct
9 Correct 17 ms 22400 KB Output is correct
10 Correct 18 ms 22400 KB Output is correct
11 Correct 19 ms 22400 KB Output is correct
12 Correct 18 ms 22420 KB Output is correct
13 Correct 19 ms 22400 KB Output is correct
14 Correct 18 ms 22400 KB Output is correct
15 Correct 18 ms 22400 KB Output is correct
16 Correct 18 ms 22400 KB Output is correct
17 Correct 19 ms 22528 KB Output is correct
18 Correct 18 ms 22400 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 22400 KB Output is correct
2 Correct 17 ms 22400 KB Output is correct
3 Correct 17 ms 22400 KB Output is correct
4 Correct 17 ms 22400 KB Output is correct
5 Correct 17 ms 22400 KB Output is correct
6 Correct 18 ms 22400 KB Output is correct
7 Correct 18 ms 22272 KB Output is correct
8 Correct 18 ms 22400 KB Output is correct
9 Correct 17 ms 22400 KB Output is correct
10 Correct 18 ms 22400 KB Output is correct
11 Correct 19 ms 22400 KB Output is correct
12 Correct 18 ms 22420 KB Output is correct
13 Correct 19 ms 22400 KB Output is correct
14 Correct 18 ms 22400 KB Output is correct
15 Correct 18 ms 22400 KB Output is correct
16 Correct 18 ms 22400 KB Output is correct
17 Correct 19 ms 22528 KB Output is correct
18 Correct 18 ms 22400 KB Output is correct
19 Correct 41 ms 23040 KB Output is correct
20 Correct 42 ms 23168 KB Output is correct
21 Correct 49 ms 23168 KB Output is correct
22 Correct 53 ms 23296 KB Output is correct
23 Correct 63 ms 25768 KB Output is correct
24 Correct 80 ms 26488 KB Output is correct
25 Correct 88 ms 27000 KB Output is correct
26 Correct 96 ms 27648 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 22324 KB Output is correct
2 Correct 18 ms 22272 KB Output is correct
3 Correct 19 ms 22400 KB Output is correct
4 Correct 30 ms 22528 KB Output is correct
5 Correct 79 ms 23488 KB Output is correct
6 Correct 18 ms 22272 KB Output is correct
7 Correct 19 ms 22400 KB Output is correct
8 Correct 19 ms 22400 KB Output is correct
9 Correct 20 ms 22528 KB Output is correct
10 Correct 36 ms 22776 KB Output is correct
11 Correct 101 ms 23800 KB Output is correct
12 Correct 22 ms 23552 KB Output is correct
13 Correct 22 ms 23296 KB Output is correct
14 Correct 24 ms 23424 KB Output is correct
15 Correct 44 ms 23672 KB Output is correct
16 Correct 127 ms 24872 KB Output is correct
17 Correct 141 ms 42904 KB Output is correct
18 Correct 139 ms 42856 KB Output is correct
19 Correct 148 ms 42856 KB Output is correct
20 Correct 192 ms 43108 KB Output is correct
21 Correct 491 ms 44520 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23040 KB Output is correct
2 Correct 55 ms 23168 KB Output is correct
3 Correct 194 ms 23932 KB Output is correct
4 Correct 359 ms 24440 KB Output is correct
5 Correct 60 ms 31224 KB Output is correct
6 Correct 119 ms 31352 KB Output is correct
7 Correct 381 ms 32008 KB Output is correct
8 Correct 728 ms 32956 KB Output is correct
9 Correct 267 ms 72428 KB Output is correct
10 Correct 386 ms 72560 KB Output is correct
11 Correct 871 ms 73280 KB Output is correct
12 Correct 1515 ms 74120 KB Output is correct
13 Correct 560 ms 127460 KB Output is correct
14 Correct 696 ms 127900 KB Output is correct
15 Correct 1296 ms 128464 KB Output is correct
16 Correct 2102 ms 129288 KB Output is correct
17 Correct 4177 ms 129180 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3590 ms 118316 KB Output is correct
2 Correct 3770 ms 120552 KB Output is correct
3 Correct 3592 ms 119256 KB Output is correct
4 Correct 3823 ms 120852 KB Output is correct
5 Correct 3546 ms 115484 KB Output is correct
6 Correct 3192 ms 93960 KB Output is correct
7 Correct 4698 ms 139916 KB Output is correct
8 Correct 4574 ms 140344 KB Output is correct
9 Correct 4677 ms 140312 KB Output is correct
10 Correct 4751 ms 139552 KB Output is correct
11 Correct 4845 ms 134176 KB Output is correct
12 Correct 4110 ms 105576 KB Output is correct
13 Execution timed out 5069 ms 150632 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 22400 KB Output is correct
2 Correct 17 ms 22400 KB Output is correct
3 Correct 17 ms 22400 KB Output is correct
4 Correct 17 ms 22400 KB Output is correct
5 Correct 17 ms 22400 KB Output is correct
6 Correct 18 ms 22400 KB Output is correct
7 Correct 18 ms 22272 KB Output is correct
8 Correct 18 ms 22400 KB Output is correct
9 Correct 17 ms 22400 KB Output is correct
10 Correct 18 ms 22400 KB Output is correct
11 Correct 19 ms 22400 KB Output is correct
12 Correct 18 ms 22420 KB Output is correct
13 Correct 19 ms 22400 KB Output is correct
14 Correct 18 ms 22400 KB Output is correct
15 Correct 18 ms 22400 KB Output is correct
16 Correct 18 ms 22400 KB Output is correct
17 Correct 19 ms 22528 KB Output is correct
18 Correct 18 ms 22400 KB Output is correct
19 Correct 41 ms 23040 KB Output is correct
20 Correct 42 ms 23168 KB Output is correct
21 Correct 49 ms 23168 KB Output is correct
22 Correct 53 ms 23296 KB Output is correct
23 Correct 63 ms 25768 KB Output is correct
24 Correct 80 ms 26488 KB Output is correct
25 Correct 88 ms 27000 KB Output is correct
26 Correct 96 ms 27648 KB Output is correct
27 Correct 17 ms 22324 KB Output is correct
28 Correct 18 ms 22272 KB Output is correct
29 Correct 19 ms 22400 KB Output is correct
30 Correct 30 ms 22528 KB Output is correct
31 Correct 79 ms 23488 KB Output is correct
32 Correct 18 ms 22272 KB Output is correct
33 Correct 19 ms 22400 KB Output is correct
34 Correct 19 ms 22400 KB Output is correct
35 Correct 20 ms 22528 KB Output is correct
36 Correct 36 ms 22776 KB Output is correct
37 Correct 101 ms 23800 KB Output is correct
38 Correct 22 ms 23552 KB Output is correct
39 Correct 22 ms 23296 KB Output is correct
40 Correct 24 ms 23424 KB Output is correct
41 Correct 44 ms 23672 KB Output is correct
42 Correct 127 ms 24872 KB Output is correct
43 Correct 141 ms 42904 KB Output is correct
44 Correct 139 ms 42856 KB Output is correct
45 Correct 148 ms 42856 KB Output is correct
46 Correct 192 ms 43108 KB Output is correct
47 Correct 491 ms 44520 KB Output is correct
48 Correct 24 ms 23040 KB Output is correct
49 Correct 55 ms 23168 KB Output is correct
50 Correct 194 ms 23932 KB Output is correct
51 Correct 359 ms 24440 KB Output is correct
52 Correct 60 ms 31224 KB Output is correct
53 Correct 119 ms 31352 KB Output is correct
54 Correct 381 ms 32008 KB Output is correct
55 Correct 728 ms 32956 KB Output is correct
56 Correct 267 ms 72428 KB Output is correct
57 Correct 386 ms 72560 KB Output is correct
58 Correct 871 ms 73280 KB Output is correct
59 Correct 1515 ms 74120 KB Output is correct
60 Correct 560 ms 127460 KB Output is correct
61 Correct 696 ms 127900 KB Output is correct
62 Correct 1296 ms 128464 KB Output is correct
63 Correct 2102 ms 129288 KB Output is correct
64 Correct 4177 ms 129180 KB Output is correct
65 Correct 3590 ms 118316 KB Output is correct
66 Correct 3770 ms 120552 KB Output is correct
67 Correct 3592 ms 119256 KB Output is correct
68 Correct 3823 ms 120852 KB Output is correct
69 Correct 3546 ms 115484 KB Output is correct
70 Correct 3192 ms 93960 KB Output is correct
71 Correct 4698 ms 139916 KB Output is correct
72 Correct 4574 ms 140344 KB Output is correct
73 Correct 4677 ms 140312 KB Output is correct
74 Correct 4751 ms 139552 KB Output is correct
75 Correct 4845 ms 134176 KB Output is correct
76 Correct 4110 ms 105576 KB Output is correct
77 Execution timed out 5069 ms 150632 KB Time limit exceeded
78 Halted 0 ms 0 KB -