답안 #971943

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
971943	2024-04-29T14:30:01 Z	efedmrlr	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	501 ms	510956 KB

diameter

#include <bits/stdc++.h>
#define int long long int
#define lli 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;
const int LGN = 18;

struct SegT {
    vector<lli> st, tag;
    int n;
    void build(int tl, int tr, int v, vector<int> &x) {
        if(tl == tr) {
            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);
    }
    lli 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));
    }
    lli query(int l, int r) {
        return query(0, n, 1, l, r);
    }
};
int n = 0, q = 0, w = 0;
vector<vector<array<int, 2> > > adj(N, vector<array<int, 2> >());
vector<array<int, 3> > edg;
vector<int> sub(N, 0);
vector<int> vis(N, 0);
array<SegT, LGN> st;
vector<array<int, LGN> > cent(N);
vector<array<int, LGN> > tin(N), p(N), ssz(N);
vector<array<int, LGN> > comp(N);
vector<array<int, LGN> > edgnode(N);
array<int, LGN> tim;
array<vector<int>, LGN> arr;
vector<set<array<int, 2>, greater<array<int, 2> > > > cand(N, set<array<int, 2>, greater<array<int, 2> > >());
vector<vector<array<int, 2> > > cent_adj(N, vector<array<int, 2> >());
set<array<int, 2>, greater<array<int, 2> > > anss;
vector<int> lv(N, 0);
vector<int> cent_res(N, 0);
void dfssz(int node, int par) {
    sub[node] = 1;
    for(auto c : adj[node]) {
        if(c[0] == par || vis[c[0]]) {
            continue;
        }
        dfssz(c[0], node);
        sub[node] += sub[c[0]];
    }
}
int get_cent(int node, int par, int tar) {
    for(auto c : adj[node]) {
        if(c[0] == par || vis[c[0]]) continue;
        if(sub[c[0]] * 2 > tar) {
            return get_cent(c[0], node, tar);
        }
    }
    return node;
}
void prec(int node, int par, int lvl, int centro) {
    ssz[node][lvl] = 1;
    tin[node][lvl] = tim[lvl]++;
    cent[node][lvl] = centro;
    for(auto &c : adj[node]) {
        if(c[0] == par || vis[c[0]]) continue;
        p[c[0]][lvl] = node;
        edgnode[c[1]][lvl] = c[0];
        prec(c[0], node, lvl, centro);
        ssz[node][lvl] += ssz[c[0]][lvl];
    }

}
void prec2(int node, int par, int lvl, int g) {
    comp[node][lvl] = g;
    for(auto c : adj[node]) {
        if(c[0] == par || vis[c[0]]) continue;
        prec2(c[0], node, lvl, g);
    }
}
void prec3(int node, int par, int lvl) {
    for(auto c : adj[node]) {
        if(c[0] == par || vis[c[0]]) continue;
        arr[lvl][tin[c[0]][lvl]] = arr[lvl][tin[node][lvl]] + edg[c[1]][2];
        prec3(c[0], node, lvl);
    }
}
void centroid_decomp(int node, int lvl) {
    dfssz(node, 0);
    int centro = get_cent(node, 0, sub[node]);
    lv[centro] = lvl;
    p[centro][lvl] = 0;
    prec(centro, 0, lvl, centro);
    for(auto c : adj[centro]) {
        if(vis[c[0]]) continue;
        cent_adj[centro].pb({c[0], 0});
        prec2(c[0], centro, lvl, c[0]);
    }
    arr[lvl][centro] = 0;
    prec3(centro, 0, lvl);
    
    vis[centro] = 1;
    for(auto c : adj[node]) {
        if(vis[c[0]]) continue;
        centroid_decomp(c[0], lvl + 1);
    }
}

void solve() {
    REP(i, LGN) {
        tim[i] = 0;
        arr[i].assign(N, 0);
        REP(j, N) edgnode[j][i] = -1;
    }
    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});
    }
    centroid_decomp(1, 0);
    REP(i, LGN) {
        st[i].reset(n + 1);
        st[i].build(0, st[i].n, 1, arr[i]);
    }
    for(int i = 1; i <= n; i++) {
        sort(all(cent_adj[i]));
        for(auto &c : cent_adj[i]) {
            int v = st[lv[i]].query(tin[c[0]][lv[i]], tin[c[0]][lv[i]] + ssz[c[0]][lv[i]] - 1);
            cand[i].insert({v, c[0]});
            c[1] = v;
        }
        cand[i].insert({0, -1});
        cand[i].insert({0, -2});
        cent_res[i] = (*cand[i].begin())[0] + (*next(cand[i].begin()))[0];
        anss.insert({cent_res[i], i});
    }

    int last = 0;
    REP(z, q) {
        int d, e;
        cin >> d >> e;
        d = (d + last) % (n - 1);
        e = (e + last) % w;
        
        for(int i = 0; i < LGN; i++) {
            if(edgnode[d][i] == -1) continue;
            int node = edgnode[d][i];
            int centr = cent[node][i];
            int rep = comp[node][i];
            auto itr = lower_bound(all(cent_adj[centr]), array<int, 2>({rep, 0}));
            assert(rep == (*itr)[0]);
            cand[centr].erase({(*itr)[1], rep});
            st[i].update(tin[node][i], tin[node][i] + ssz[node][i] - 1, e - edg[d][2]);
            edg[d][2] = e;
            (*itr)[1] = st[i].query(tin[rep][i], tin[rep][i] + ssz[rep][i] - 1);
            cand[centr].insert({(*itr)[1], rep});
            
            anss.erase({cent_res[centr], centr});
            cent_res[centr] = (*cand[centr].begin())[0] + (*next(cand[centr].begin()))[0];
            anss.insert({cent_res[centr], centr});
        }
        last = (*anss.begin())[0];
        cout << last << "\n";
    }

}

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

Subtask #1
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	58 ms	111780 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	58 ms	111780 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	111556 KB	Output is correct
2	Correct	31 ms	111704 KB	Output is correct
3	Correct	31 ms	111708 KB	Output is correct
4	Correct	40 ms	111832 KB	Output is correct
5	Correct	84 ms	112712 KB	Output is correct
6	Correct	30 ms	111444 KB	Output is correct
7	Correct	31 ms	112212 KB	Output is correct
8	Correct	32 ms	112228 KB	Output is correct
9	Correct	32 ms	112476 KB	Output is correct
10	Correct	46 ms	112544 KB	Output is correct
11	Correct	127 ms	113724 KB	Output is correct
12	Correct	37 ms	119132 KB	Output is correct
13	Correct	37 ms	119120 KB	Output is correct
14	Correct	39 ms	119120 KB	Output is correct
15	Correct	67 ms	119376 KB	Output is correct
16	Correct	151 ms	120656 KB	Output is correct
17	Correct	213 ms	259240 KB	Output is correct
18	Correct	199 ms	259136 KB	Output is correct
19	Correct	197 ms	259416 KB	Output is correct
20	Correct	258 ms	259808 KB	Output is correct
21	Correct	462 ms	260852 KB	Output is correct