Submission #1113617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113617		ShaShi	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	5077 ms	48488 KiB

diameter

#include <bits/stdc++.h>
 
#define int long long  

// #pragma GCC  ("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
 
#define F first 
#define S second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << "\n", exit(0);
#define pii pair<int, int>
#define pll pair<long long, long long>
#define endl "\n"
 
 
 
using namespace std;
typedef long long ll;
typedef __int128_t lll;
typedef long double ld;
 
 
const int MAXN = (int)1e5 + 7;
const ll MOD = (int)1e9 + 7;
const int INF = (int)1e9 + 7;
const int LG = 17;
const int SQ = 230;


int n, m, k, t, tmp, tmp2, tmp3, tmp4, u, v, w, flag, q, ans, W, last;
int arr[MAXN], st[MAXN], ft[MAXN], _h[MAXN], depth[MAXN], par[MAXN], weight[MAXN], sz[MAXN], root_cost[MAXN];
int pow2dad[MAXN][LG], counter, par_id[MAXN];
pii edge[MAXN], zir[MAXN], bala[MAXN], out_max[MAXN];
bool khar[MAXN], is_changed[MAXN], edge_changed[MAXN];
vector<pii> adj[MAXN], st_sorted;
vector<pair<int, pii>> vec[MAXN];
vector<int> G[MAXN], changed;



inline pii merge(pii x, pii y) {
    if (x.F > y.F) return x;
    return y;
}


inline bool is_ancestor(int v, int u) { return (st[v] <= st[u] && ft[v] >= ft[u]); }


void DFSsz(int v) {
    st[v] = flag++; sz[v] = 1;

    for (auto cur:adj[v]) {
        int u = cur.F, ind = cur.S;

        if (u == par[v]) continue;

        par[u] = v; depth[u] = depth[v]+1; par_id[u] = ind;

        DFSsz(u);

        sz[v] += sz[u];
    }

    ft[v] = flag;
}


inline int up(int v, int k) {
    for (int i=LG-1; i>=0; i--) {
        if (k >= (1<<i)) {
            k -= (1<<i);
            v = pow2dad[v][i];
        }
    }

    return v;
}


inline int LCA(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);

    u = up(u, depth[u]-depth[v]);

    for (int i=LG-1; i>=0; i--) {
        if (depth[u] >= (1<<i) && pow2dad[u][i] != pow2dad[v][i]) {
            u = pow2dad[u][i];
            v = pow2dad[v][i];
        }
    }

    if (u == v) return u;
    return par[v];
}



void DFSzir(int v) {
    zir[v] = {0, v};

    for (auto cur:adj[v]) {
        int u = cur.F, ind = cur.S;

        if (u == par[v]) continue;

        root_cost[u] = root_cost[v]+weight[ind];

        DFSzir(u);

        zir[v] = merge(zir[v], {zir[u].F+weight[ind], zir[u].S});
        vec[v].pb({zir[u].F+weight[ind], {zir[u].S, ind}});
    }
}


void DFSbala(int v) {
    pii cur = {0, v};

    for (int i=0; i<adj[v].size(); i++) {
        int u = adj[v][i].F, ind = adj[v][i].S;

        if (u == par[v]) continue;

        bala[u] = merge(bala[u], cur);
        cur = merge(cur, {zir[u].F+weight[ind], zir[u].S});
    }

    cur = {0, v};

    for (int i=adj[v].size()-1; i>=0; i--) {
        int u = adj[v][i].F, ind = adj[v][i].S;

        if (u == par[v]) continue;

        bala[u] = merge(bala[u], cur);
        cur = merge(cur, {zir[u].F+weight[ind], zir[u].S});
    }


    for (int i=0; i<adj[v].size(); i++) {
        int u = adj[v][i].F, ind = adj[v][i].S;

        if (u == par[v]) continue;

        vec[u].pb({bala[u].F+weight[ind], {bala[u].S, ind}});

        DFSbala(u);
    }
}


inline void calculate_stuff() {
    fill_n(is_changed, n+7, 0); fill_n(edge_changed, n+7, 0);
    for (int i=1; i<=n; i++) vec[i].clear(); changed.clear();

    DFSzir(1); bala[1] = {0, 1}; DFSbala(1);

    for (int i=1; i<=n; i++) sort(all(vec[i]), greater<pair<int, pii>>());
}


inline void add_G_edge(int u, int v) {
    // cout << "! " << u << " " << v << endl;
    G[u].pb(v); G[v].pb(u);
}


void make_the_tree(int v) {
    while (1) {
        if (counter == st_sorted.size()) return;

        if (is_ancestor(v, st_sorted[counter].S)) {
            add_G_edge(v, st_sorted[counter].S); counter++;
            make_the_tree(st_sorted[counter-1].S);
        } else return;
    }
}


inline int first_on_path_id(int u, int v) {
    if (is_ancestor(v, u)) return par_id[u];
    return par_id[up(v, depth[v]-depth[u]-1)];
}


pii fucking_res;
int fucking_dist;


inline int path_cost(int u, int v) {
    if (u == v) return 0;
    if (depth[u] < depth[v]) swap(u, v);
    if (depth[u]-depth[v] == 1) return weight[par_id[u]];
    return root_cost[u]-root_cost[v];
}


void DFSspecial(int v, int p=-1) {
    fucking_res = merge(fucking_res, {fucking_dist+out_max[v].F, out_max[v].S});

    for (int u:G[v]) {
        if (u == p) continue;

        int tmp = path_cost(v, u);

        fucking_dist += tmp;

        DFSspecial(u, v);

        fucking_dist -= tmp;
    }
}

inline pii get_door_most(int v) {
    st_sorted.clear();
    for (auto cur:changed) st_sorted.pb({st[cur], cur});
    st_sorted.pb({st[v], v}); st_sorted.pb({st[1], 1});

    sort(all(st_sorted));
    st_sorted.resize(unique(all(st_sorted))-st_sorted.begin());

    for (auto cur:st_sorted) G[cur.S].clear();

    // for (auto cur:st_sorted) cout << cur.S << endl;

    counter = 1;

    make_the_tree(st_sorted[0].S);


    // exit(0);

    for (auto cur:st_sorted) {
        int u = cur.S;

        vector<int> temp;

        for (int w:G[u]) temp.pb(first_on_path_id(u, w));

        for (int w:temp) khar[w] = 1;

        out_max[u] = {0, u};

        for (int i=0; i<vec[u].size(); i++) {
            if (khar[vec[u][i].S.S]) continue;

            out_max[u] = {vec[u][i].F, vec[u][i].S.F}; break;
        }

        for (int w:temp) khar[w] = 0;
    }

    fucking_res = {0, v}; fucking_dist = 0;

    DFSspecial(v);

    // cout << "# " << fucking_res.F << " " << fucking_res.S << endl;

    return fucking_res;
}


int32_t main() {
    #ifdef LOCAL
    freopen("inp.in", "r", stdin);
    freopen("res.out", "w", stdout);
    #else
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif

    cin >> n >> q >> W;

    for (int i=1; i<n; i++) {
        cin >> u >> v >> w;

        adj[u].pb({v, i}); adj[v].pb({u, i}); 
        weight[i] = w; edge[i] = {u, v};
    }

    DFSsz(1);

    for (int i=1; i<=n; i++) pow2dad[i][0] = par[i];
    for (int j=1; j<LG; j++) for (int i=1; i<=n; i++) pow2dad[i][j] = pow2dad[pow2dad[i][j-1]][j-1];

    last = 0;


    // calculate_stuff();
    // for (int i=1; i<=n; i++) {
    //     cout << "! " << i << endl;

    //     for (auto cur:vec[i]) {
    //         cout << cur.S.S << " : " << cur.S.F << " " << cur.F << endl;
    //     }
    // }
    // exit(0);


    for (int i=0; i<q; i++) {
        if (!(i%SQ)) calculate_stuff();

        cin >> u >> w;
        
        u = (u+last)%(n-1) + 1;
        w = (w+last)%W;

        weight[u] = w; edge_changed[u] = 1;

        if (!is_changed[edge[u].F]) changed.pb(edge[u].F), is_changed[edge[u].F] = 1;
        if (!is_changed[edge[u].S]) changed.pb(edge[u].S), is_changed[edge[u].S] = 1;

        cout << (last = get_door_most(get_door_most(1).S).F) << endl;
    }

    return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'void DFSbala(long long int)':
diameter.cpp:124:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for (int i=0; i<adj[v].size(); i++) {
      |                   ~^~~~~~~~~~~~~~
diameter.cpp:145:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |     for (int i=0; i<adj[v].size(); i++) {
      |                   ~^~~~~~~~~~~~~~
diameter.cpp: In function 'void calculate_stuff()':
diameter.cpp:159:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  159 |     for (int i=1; i<=n; i++) vec[i].clear(); changed.clear();
      |     ^~~
diameter.cpp:159:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  159 |     for (int i=1; i<=n; i++) vec[i].clear(); changed.clear();
      |                                              ^~~~~~~
diameter.cpp: In function 'void make_the_tree(long long int)':
diameter.cpp:175:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |         if (counter == st_sorted.size()) return;
      |             ~~~~~~~~^~~~~~~~~~~~~~~~~~~
diameter.cpp: In function 'std::pair<long long int, long long int> get_door_most(long long int)':
diameter.cpp:249:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  249 |         for (int i=0; i<vec[u].size(); i++) {
      |                       ~^~~~~~~~~~~~~~

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