oj.uz

답안 #971677

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
971677 2024-04-29T07:32:31 Z efedmrlr Dynamic Diameter (CEOI19_diameter) C++17
31 / 100
 261 ms 43376 KB 
#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) {
            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];
        // cout << "c1:" << c[1] << " c[0]:" <<c[0] << "\n";
        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});
        // cout << "d:" << d << "\n";

        // cout << "nd :" << nd << " curs:" << curs << "\n";
        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});
        auto itr = cand.end();
        itr--;
        int ans = (*itr)[0];
        if(cand.size() > 1) {
            itr--;
            ans += (*itr)[0];
        }
        // cout << "cands:\n";
        // for(auto c : cand) {
        //     cout << c[0] << " " << c[1] << "\n";
        // }
        cout << ans << "\n";
        last = ans;
    }
}

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

Subtask #1
0 / 11.0

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

Subtask #2
0 / 13.0

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

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8284 KB Output is correct
2 Correct 4 ms 8284 KB Output is correct
3 Correct 4 ms 8340 KB Output is correct
4 Correct 12 ms 8540 KB Output is correct
5 Correct 44 ms 9228 KB Output is correct
6 Correct 4 ms 8284 KB Output is correct
7 Correct 4 ms 8284 KB Output is correct
8 Correct 4 ms 8284 KB Output is correct
9 Correct 5 ms 8284 KB Output is correct
10 Correct 16 ms 8540 KB Output is correct
11 Correct 62 ms 9548 KB Output is correct
12 Correct 7 ms 9304 KB Output is correct
13 Correct 7 ms 9308 KB Output is correct
14 Correct 10 ms 9308 KB Output is correct
15 Correct 22 ms 9652 KB Output is correct
16 Correct 90 ms 10580 KB Output is correct
17 Correct 74 ms 28892 KB Output is correct
18 Correct 75 ms 28844 KB Output is correct
19 Correct 77 ms 29108 KB Output is correct
20 Correct 107 ms 29176 KB Output is correct
21 Correct 261 ms 30636 KB Output is correct

Subtask #4
0 / 18.0

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

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 27220 KB Output is correct
2 Correct 173 ms 27372 KB Output is correct
3 Correct 207 ms 27736 KB Output is correct
4 Correct 156 ms 27884 KB Output is correct
5 Correct 214 ms 28332 KB Output is correct
6 Correct 170 ms 30512 KB Output is correct
7 Correct 231 ms 33768 KB Output is correct
8 Correct 178 ms 33628 KB Output is correct
9 Correct 173 ms 33764 KB Output is correct
10 Correct 212 ms 33612 KB Output is correct
11 Correct 174 ms 34108 KB Output is correct
12 Correct 190 ms 34956 KB Output is correct
13 Correct 207 ms 43140 KB Output is correct
14 Correct 238 ms 43240 KB Output is correct
15 Correct 229 ms 43376 KB Output is correct
16 Correct 197 ms 43212 KB Output is correct
17 Correct 199 ms 42192 KB Output is correct
18 Correct 202 ms 38384 KB Output is correct
19 Correct 194 ms 43104 KB Output is correct
20 Correct 223 ms 43280 KB Output is correct
21 Correct 199 ms 43312 KB Output is correct
22 Correct 188 ms 43296 KB Output is correct
23 Correct 228 ms 42292 KB Output is correct
24 Correct 185 ms 38248 KB Output is correct

Subtask #6
0 / 27.0

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