Submission #446283

#	Time	Username	Problem	Language	Result	Execution time	Memory
446283		qwerasdfzxcl	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	2977 ms	270928 KiB

diameter

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#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;
unordered_map<int, pair<int, int>> mp[100100];
unordered_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 (stderr)

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

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