Submission #446276

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
446276	2021-07-21T12:19:17 Z	qwerasdfzxcl	Dynamic Diameter (CEOI19_diameter)	C++14	7 / 100	3674 ms	223300 KB

diameter

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

using namespace std;
struct Node{
    int x, y, w, nxt;
    Node(){}
    Node(int _x, int _y, int _w, int _nxt):x(_x), y(_y), w(_w), nxt(_nxt){}
};
Node combine(Node x, Node y){
    if (x.w>=y.w) return x;
    return y;
}
struct Seg{
    vector<Node> tree;
    vector<int> lazy;
    int sz;
    void make_tree(int n){
        sz = n;
        tree.resize(sz*4+4);
        lazy.resize(sz*4+4, 0);
    }
    void init(int i, int l, int r, vector<Node> &vec){
        if (l==r){
            tree[i] = vec[l];
            return;
        }
        int m = (l+r)>>1;
        init(i<<1, l, m, vec); init(i<<1|1, m+1, r, vec);
        tree[i] = combine(tree[i<<1], tree[i<<1|1]);
    }
    void propagate(int i, int l, int r){
        tree[i].w += lazy[i];
        if (l!=r){
            lazy[i<<1] = lazy[i];
            lazy[i<<1|1] = lazy[i];
        }
        lazy[i] = 0;
    }
    void update(int i, int l, int r, int s, int e, int val){
        propagate(i, l, r);
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            lazy[i] += val; propagate(i, l, r); return;
        }
        int m = (l+r)>>1;
        update(i<<1, l, m, s, e, val); update(i<<1|1, m+1, r, s, e, val);
        tree[i] = combine(tree[i<<1], tree[i<<1|1]);
    }
    Node query(int i, int l, int r, int s, int e){
        if (s>e) return Node(0, 0, -9e18, 0);
        propagate(i, l, r);
        if (r<s || e<l) return Node(0, 0, -9e18, 0);
        if (s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        Node ret = query(i<<1, l, m, s, e);
        ret = combine(ret, query(i<<1|1, m+1, r, s, e));
        return ret;
    }
}tree[100100];
struct Edge{
    int s, e, x;
    Edge(){}
    Edge(int _s, int _e, int _x): s(_s), e(_e), x(_x){}
    int nxt(int val){
        if (s==val) return e;
        return s;
    }
}e[100100];
vector<int> adj[100100], g[100100];
int sz[100100];
bool cent_visited[100100];

void getsz(int s, int pa){
    sz[s] = 1;
    for (auto &v:adj[s]){
        int nxt = e[v].nxt(s);
        if (nxt==pa || cent_visited[nxt]) continue;
        getsz(nxt, s);
        sz[s] += sz[nxt];
    }
}

int getcent(int s, int pa, int mx){
    for (auto &v:adj[s]){
        int nxt = e[v].nxt(s);
        if (nxt==pa || cent_visited[nxt]) continue;
        if (sz[nxt]*2>mx) return getcent(nxt, s, mx);
    }
    return s;
}

int cnt;
vector<Node> vec;
map<int, pair<int, int>> mp[100100];
map<int, int> mp2[100100];
pair<int, int> ran[100100];

pair<int, int> dfs(int s, int pa, int val, int cent){
    pair<int, int> ret = {9e18, -9e18};
    for (auto &v:adj[s]){
        int nxt = e[v].nxt(s);
        if (nxt==pa || cent_visited[nxt]) continue;
        auto p = dfs(nxt, s, val+e[v].x, cent);
        ret.first = min(ret.first, p.first);
        ret.second = max(ret.second, p.second);

        mp[cent][v] = p;
        if (cent==s){
            ran[cnt] = p;
            cnt++;
        }
        else{
            mp2[cent][v] = cnt;
        }
    }
    if (ret.first==9e18){
        vec.emplace_back(0, 0, val, cnt);
        return make_pair((int)vec.size()-1, (int)vec.size()-1);
    }
    return ret;
}

int getcentree(int s){
    getsz(s, -1);
    if (sz[s]==1) return s;
    int cent = getcent(s, -1, sz[s]);
    cnt = 0;
    vec.clear();
    auto p = dfs(cent, -1, 0, cent);
    for (auto &N:vec) N.x = ran[N.nxt].first, N.y = ran[N.nxt].second;
    //for (auto &N:vec) printf("%lld %lld %lld %lld\n", N.x, N.y, N.w, N.nxt);
    //printf("%lld %lld\n", p.first, p.second);
    tree[cent].make_tree((int)vec.size());
    tree[cent].init(1, 0, p.second, vec);

    cent_visited[cent] = 1;
    for (auto &v:adj[cent]){
        int nxt = e[v].nxt(cent);
        if (cent_visited[nxt]) continue;
        int x = getcentree(nxt);
        g[cent].push_back(x);
    }
    return cent;
}

signed main(){
    int n, q, w;
    scanf("%lld %lld %lld", &n, &q, &w);
    for (int i=0;i<n-1;i++){
        scanf("%lld %lld %lld", &e[i].s, &e[i].e, &e[i].x);
        adj[e[i].s].push_back(i);
        adj[e[i].e].push_back(i);
    }

    int CENT = getcentree(1);
    /*for (int i=0;i<3;i++){
        Node tmp2 = tree[2].query(1, 0, 2, i, i);
        printf("%lld %lld %lld %lld\n", tmp2.x, tmp2.y, tmp2.w, tmp2.nxt);
    }*/

    int last = 0;
    while(q--){
        int x, y;
        scanf("%lld %lld", &x, &y);
        x = (x+last)%(n-1);
        y = (y+last)%w;
        int org = e[x].x;
        e[x].x = y;
        //printf("%lld %lld %lld\n", y, org, e[x].x);

        int pos = CENT;
        while(true){
            if (g[pos].empty()) break;
            assert(mp[pos].find(x)!=mp[pos].end());
            auto p = mp[pos][x];
            //printf("%lld %lld\n", p.first, p.second);
            tree[pos].update(1, 0, tree[pos].sz-1, p.first, p.second, y-org);
            if (mp2[pos].find(x)==mp2[pos].end()) break;
            pos = g[pos][mp2[pos][x]];
        }

        int ans = 0;
        pos = CENT;
        while(true){
            if (g[pos].empty()) break;
            auto tmp = tree[pos].query(1, 0, tree[pos].sz-1, 0, tree[pos].sz);
            //printf("%lld %lld %lld %lld\n", tmp.x, tmp.y, tmp.w, tmp.nxt);
            auto tmp2 = tree[pos].query(1, 0, tree[pos].sz-1, 0, tmp.x-1);
            //printf("%lld %lld %lld %lld\n", tmp2.x, tmp2.y, tmp2.w, tmp2.nxt);
            auto tmp3 = tree[pos].query(1, 0, tree[pos].sz-1, tmp.y+1, tree[pos].sz-1);
            //printf("%lld %lld %lld %lld\n", tmp3.x, tmp3.y, tmp3.w, tmp3.nxt);
            int val = max(tmp.w, tmp.w+max(tmp2.w, tmp3.w));
            ans = max(ans, val);
            pos = g[pos][tmp.nxt];
        }
        printf("%lld\n", ans);
        last = ans;
    }
    return 0;
}

Compilation message

diameter.cpp: In function 'int main()':
diameter.cpp:149:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |     scanf("%lld %lld %lld", &n, &q, &w);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:151:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |         scanf("%lld %lld %lld", &e[i].s, &e[i].e, &e[i].x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:165:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |         scanf("%lld %lld", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	11 ms	19788 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	11 ms	19788 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	19788 KB	Output is correct
2	Correct	11 ms	19816 KB	Output is correct
3	Correct	12 ms	19908 KB	Output is correct
4	Correct	24 ms	20080 KB	Output is correct
5	Correct	73 ms	20916 KB	Output is correct
6	Correct	11 ms	19788 KB	Output is correct
7	Correct	12 ms	20032 KB	Output is correct
8	Correct	11 ms	20028 KB	Output is correct
9	Correct	13 ms	20044 KB	Output is correct
10	Correct	34 ms	20236 KB	Output is correct
11	Correct	123 ms	21304 KB	Output is correct
12	Correct	17 ms	21576 KB	Output is correct
13	Correct	15 ms	21524 KB	Output is correct
14	Correct	18 ms	21668 KB	Output is correct
15	Correct	46 ms	21832 KB	Output is correct
16	Correct	174 ms	23044 KB	Output is correct
17	Correct	90 ms	52188 KB	Output is correct
18	Correct	91 ms	52120 KB	Output is correct
19	Correct	95 ms	52148 KB	Output is correct
20	Correct	146 ms	52280 KB	Output is correct
21	Correct	391 ms	52772 KB	Output is correct