Submission #971658

#	Time	Username	Problem	Language	Result	Execution time	Memory
971658		efedmrlr	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	192 ms	27844 KiB

diameter

#include <bits/stdc++.h>
#define int long long int
#define pb push_back
#define MP make_pair
#define ld long double
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 1e5 + 5;
const int INF = 1e9 + 500;

struct SegT {
    vector<int> st, tag;
    int n;
    void build(int tl, int tr, int v, vector<int> &x) {
        if(tl == tr) {
            if(x.size() <= tl) return;
            st[v] = x[tl];
            return;
        }
        int tm = (tl + tr) >> 1;
        build(tl, tm, v << 1, x);
        build(tm + 1, tr, v << 1 ^ 1, x);
        st[v] = max(st[v << 1], st[v << 1 ^ 1]);
    }
    void reset(int nn) {
        n = nn;
        st.assign(4*(n + 3), 0);
        tag.assign(4*(n + 3), 0);
    }
    void push(int v) {
        st[v << 1] += tag[v];
        st[v << 1 ^ 1] += tag[v];

        tag[v << 1] += tag[v];
        tag[v << 1 ^ 1] += tag[v];
        tag[v] = 0;
    }
    void update(int tl, int tr, int v, int l, int r, int val) {
        if(tl >= l && tr <= r) {
            st[v] += val;
            tag[v] += val;
            return;
        }
        if(tl > r || tr < l) {
            return;
        }
        push(v);
        int tm = (tl + tr) >> 1;
        update(tl, tm, v << 1, l, r, val);
        update(tm + 1, tr, v << 1 ^ 1, l, r, val);
        st[v] = max(st[v << 1], st[v << 1 ^ 1]);
    }
    void update(int l, int r, int val) {
        update(0, n, 1, l, r, val);
    }
    int query(int tl, int tr, int v, int l, int r) {
        if(tl >= l && tr <= r) {
            return st[v];
        }
        if(tl > r || tr < l) {
            return 0;
        }
        push(v);
        int tm = (tl + tr) >> 1;
        return max(query(tl, tm, v << 1, l, r), query(tm + 1, tr, v << 1 ^ 1, l, r));
    }
    int query(int l, int r) {
        return query(0, n, 1, l, r);
    }
};
int n, q, w;
vector<vector<array<int, 2> > > adj(N, vector<array<int, 2> >());
vector<array<int, 3> > edg;
vector<int> sub_node(N, 0);
vector<int> tin(N), p(N), sub(N, 1);
set<array<int, 2> > cand;
vector<int> arr(N, 0);
vector<int> subt(N, 0);
SegT st;
vector<int> curv(N, 0);
int tim;
void prec(int node) {
    sub[node] = 1;
    tin[node] = tim++;
    for(auto &c : adj[node]) {
        p[c[0]] = node;
        sub_node[c[1]] = c[0];
        adj[c[0]].erase(find(all(adj[c[0]]), array<int,2>({node, c[1]})));
        prec(c[0]);
        sub[node] += sub[c[0]];
    }
}
void dfs(int node) {
    
    for(auto c : adj[node]) {
        arr[tin[c[0]]] = arr[tin[node]] + edg[c[1]][2];
        dfs(c[0]);    
    }
}
void dfs2(int node, int g) {
    subt[node] = g;
    for(auto c : adj[node]) {
        dfs2(c[0], g);
    }
}
void init() {
    tim = 0;
    st.reset(n + 1);
    prec(1);
    dfs(1);
    st.build(0, st.n, 1, arr);
    cand.clear();
    for(auto c : adj[1]) {
        dfs2(c[0], c[0]);
        int v = st.query(tin[c[0]], tin[c[0]] + sub[c[0]] - 1);
        cand.insert({v, c[0]});
        curv[c[0]] = v;
    }

}   

void solve() {
    cin >> n >> q >> w;
    edg.resize(n - 1);
    REP(i, n - 1) {
        cin >> edg[i][0] >> edg[i][1] >> edg[i][2];
        adj[edg[i][0]].pb({edg[i][1], i});
        adj[edg[i][1]].pb({edg[i][0], i});
    }
    init();
    int last = 0;
    REP(z, q) {
        int d, e;
        cin >> d >> e;
        d = (d + last) % (n - 1);
        e = (e + last) % w;
        // cout << d << " " << e << " de\n";
        int nd = sub_node[d];
        int curs = subt[nd];
        cand.erase({curv[curs], curs});
        st.update(tin[nd], tin[nd] + sub[nd] - 1, e - edg[d][2]);
        edg[d][2] = e;
        curv[curs] = st.query(tin[curs], tin[curs] + sub[curs] - 1);
        cand.insert({curv[curs], curs});
        int ans = (*cand.begin())[0];
        if(cand.size() > 1) {
            ans += (*next(cand.begin()))[0];
        }
        cout << ans << "\n";
        last = ans;
    }
}

signed main() {
    fastio();
    solve();
}

Compilation message (stderr)

diameter.cpp: In member function 'void SegT::build(long long int, long long int, long long int, std::vector<long long int>&)':
diameter.cpp:25:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   25 |             if(x.size() <= tl) return;
      |                ~~~~~~~~~^~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27