oj.uz

답안 #945068

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
945068 2024-03-13T11:16:32 Z Vladth11 Dynamic Diameter (CEOI19_diameter) C++14
11 / 100
 5000 ms 39972 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const ll NMAX = 100002;
const ll INF = (1LL << 58);
const ll nrbits = 18;
const ll MOD = 998244353;

vector <int> v[NMAX];
pii diameter;
ll lung;
int dp[nrbits + 1][NMAX];
ll lazy[NMAX * 4];
pii aint[NMAX * 4];
pii timp[NMAX];
int stamp;
int n;

void propaga(int node, int st, int dr) {
    if(st != dr) {
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
    }
    aint[node].first += lazy[node];
    lazy[node] = 0;
}

pii combine(pii a, pii b) {
    return max(a, b);
}

void update(int node, int st, int dr, int a, int b, ll val) {
    propaga(node, st, dr);
    if(a <= st && dr <= b) {
        lazy[node] += val;
        return;
    }
    int mid = (st + dr) / 2;
    if(a <= mid)
        update(node * 2, st, mid, a, b, val);
    if(b > mid)
        update(node * 2 + 1, mid + 1, dr, a, b, val);
    propaga(node * 2, st, mid);
    propaga(node * 2 + 1, mid + 1, dr);
    aint[node] = combine(aint[node * 2], aint[node * 2 + 1]);
}

pii query(int node, int st, int dr, int a, int b) {
    propaga(node, st, dr);
    if(a <= st && dr <= b) {
        return aint[node];
    }
    int mid = (st + dr) / 2;
    pii sol = {0, 0};
    if(a <= mid) {
        sol = combine(sol, query(node * 2, st, mid, a, b));
    }
    if(b > mid) {
        sol = combine(sol, query(node * 2 + 1, mid + 1, dr, a, b));
    }
    return sol;
}

struct edge {
    int a, b;
    ll c;
} edges[NMAX];

int preorder[NMAX];

void build(int node, int st, int dr) {
    if(st == dr) {
        aint[node].second = preorder[st];
        return;
    }
    int mid = (st + dr) / 2;
    build(node * 2, st, mid);
    build(node * 2 + 1, mid + 1, dr);
}

void DFS(int node, int p) {
    timp[node].first = ++stamp;
    preorder[stamp] = node;
    dp[0][node] = p;
    for(auto x : v[node]) {
        if(x == p) continue;
        DFS(x, node);
    }
    timp[node].second = stamp;
}

bool isParent(int a, int b) {
    return timp[a].first <= timp[b].first && timp[b].second <= timp[a].second;
}

int LCA(int a, int b) {
    int r = b, pas = nrbits;
    while(pas >= 0) {
        int nxt = dp[pas][r];
        if(nxt != 0 && !isParent(nxt, a)) {
            r = nxt;
        }
        pas--;
    }
    if(!isParent(r, a)) {
        r = dp[0][r];
    }
    return r;
}

ll lgt(int a, int b) {
    int lca = LCA(a, b);
    return query(1, 1, n, timp[a].first, timp[a].first).first + query(1, 1, n, timp[b].first, timp[b].first).first - 2 * query(1, 1, n, timp[lca].first, timp[lca].first).first;
}

void extend(int i) {
    pii initial = diameter;
    // debugs(i);
    int prim = lgt(diameter.first, i);
    int sec = lgt(diameter.second, i);
    //debugs(prim);
    //  debug(sec);
    if(lung < prim) {
        lung = prim;
        diameter = {initial.first, i};
    }
    if(lung < sec) {
        lung = sec;
        diameter = {initial.second, i};
    }
}

int main() {
#ifdef HOME
    ifstream cin(".in");
    ofstream cout(".out");
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int q, w, i;
    cin >> n >> q >> w;
    for(i = 1; i < n; i++) {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        v[a].push_back(b);
        v[b].push_back(a);
        edges[i] = {a, b, c};
    }
    DFS(1, 0);
    for(int j = 1; j <= nrbits; j++) {
        for(i = 1; i <= n; i++) {
            dp[j][i] = dp[j - 1][dp[j - 1][i]];
        }
    }
    build(1, 1, n);
    for(i = 1; i < n; i++) {
        if(dp[0][edges[i].a] == edges[i].b) {
            swap(edges[i].a, edges[i].b);
        }
        update(1, 1, n, timp[edges[i].b].first, timp[edges[i].b].second, edges[i].c);
    }
    diameter = {1, 2};
    lung = lgt(1, 2);
    for(int j = 1; j <= n; j++) {
        extend(j);
    }
    ll last = 0;
    for(i = 1; i <= q; i++) {
        ll a, b;
        cin >> a >> b;
        a += last;
        a %= (n - 1);
        b += last;
        b %= w;
        a++;
        update(1, 1, n, timp[edges[a].b].first, timp[edges[a].b].second, b - edges[a].c);
        edges[a].c = b;
        lung = lgt(diameter.first, diameter.second);
         for(int j = 1; j <= n; j++) {
        extend(j);
    }
        last = lung;
        cout << lung << "\n";
    }
    return 0;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14752 KB Output is correct
7 Correct 4 ms 14684 KB Output is correct
8 Correct 5 ms 14784 KB Output is correct
9 Correct 4 ms 14684 KB Output is correct
10 Correct 4 ms 14680 KB Output is correct
11 Correct 4 ms 14684 KB Output is correct
12 Correct 4 ms 14684 KB Output is correct
13 Correct 6 ms 14760 KB Output is correct
14 Correct 6 ms 14684 KB Output is correct
15 Correct 6 ms 14684 KB Output is correct
16 Correct 6 ms 14680 KB Output is correct
17 Correct 6 ms 14684 KB Output is correct
18 Correct 6 ms 14684 KB Output is correct

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14752 KB Output is correct
7 Correct 4 ms 14684 KB Output is correct
8 Correct 5 ms 14784 KB Output is correct
9 Correct 4 ms 14684 KB Output is correct
10 Correct 4 ms 14680 KB Output is correct
11 Correct 4 ms 14684 KB Output is correct
12 Correct 4 ms 14684 KB Output is correct
13 Correct 6 ms 14760 KB Output is correct
14 Correct 6 ms 14684 KB Output is correct
15 Correct 6 ms 14684 KB Output is correct
16 Correct 6 ms 14680 KB Output is correct
17 Correct 6 ms 14684 KB Output is correct
18 Correct 6 ms 14684 KB Output is correct
19 Correct 2194 ms 15144 KB Output is correct
20 Correct 2304 ms 15128 KB Output is correct
21 Correct 2563 ms 15156 KB Output is correct
22 Correct 2623 ms 14932 KB Output is correct
23 Execution timed out 5040 ms 15196 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14680 KB Output is correct
3 Correct 12 ms 14684 KB Output is correct
4 Correct 87 ms 14904 KB Output is correct
5 Correct 418 ms 15804 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 6 ms 14684 KB Output is correct
8 Correct 35 ms 14684 KB Output is correct
9 Correct 321 ms 14812 KB Output is correct
10 Correct 3260 ms 15304 KB Output is correct
11 Execution timed out 5032 ms 15492 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 394 ms 14812 KB Output is correct
2 Correct 3973 ms 14984 KB Output is correct
3 Execution timed out 5018 ms 15588 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 23 ms 39972 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 3 ms 14752 KB Output is correct
7 Correct 4 ms 14684 KB Output is correct
8 Correct 5 ms 14784 KB Output is correct
9 Correct 4 ms 14684 KB Output is correct
10 Correct 4 ms 14680 KB Output is correct
11 Correct 4 ms 14684 KB Output is correct
12 Correct 4 ms 14684 KB Output is correct
13 Correct 6 ms 14760 KB Output is correct
14 Correct 6 ms 14684 KB Output is correct
15 Correct 6 ms 14684 KB Output is correct
16 Correct 6 ms 14680 KB Output is correct
17 Correct 6 ms 14684 KB Output is correct
18 Correct 6 ms 14684 KB Output is correct
19 Correct 2194 ms 15144 KB Output is correct
20 Correct 2304 ms 15128 KB Output is correct
21 Correct 2563 ms 15156 KB Output is correct
22 Correct 2623 ms 14932 KB Output is correct
23 Execution timed out 5040 ms 15196 KB Time limit exceeded
24 Halted 0 ms 0 KB -