Submission #1198856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198856		mohammadsam	Dynamic Diameter (CEOI19_diameter)	C++17	25 / 100	1962 ms	280376 KiB

diameter

/*
	in the name of god
*/
//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")

#include <bits/stdc++.h>

using namespace std;
#define int long long 
typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll ;

#define File          freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define all(V)        V.begin(),V.end()
#define setprec(x)    fixed << setprecision(x)
#define Mp(a,b)       make_pair(a,b)
#define len(V)        (int)(V.size())
#define sep           ' '
#define endl          '\n'
#define pb(x)         push_back(x)
#define fi            first
#define sec           second
#define popcount(x)   __builtin_popcount(x)
#define lid           u<<1
#define rid           (lid)|1
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 1e5 + 10,SQ=320,LOG=19;
const ll inf = 2e18 + 10 , MD = 1e9 + 7;

inline ll md(ll x){ x %= MD; return (x < 0 ? x + MD : x);}
int n , q;
int sz[N];
bool mark[N];
int par[N];
int comp[LOG][N];
int dis[LOG][N];
int lev[N];
int val[N];
vector<pii> g[N];
int mn[N];
set<pii> st[N];
vector<int> ver[N];
int ind[LOG][N],ind2[LOG][N];
vector<int> E[N];
map<pii,int> mp;
int tim[LOG];

int dfs_sz(int u,int p){
    sz[u] = 1;
    for(auto h : g[u]){
        if(h.fi!=p and !mark[h.fi]) sz[u] += dfs_sz(h.fi,u);
    }
    return sz[u];
}
int centroid(int u,int p,int S){
    for(auto h : g[u]){
        if(h.fi!=p and !mark[h.fi] and sz[h.fi] > S/2) return centroid(h.fi,u,S);
    }
    return u;
}
void dfs(int u,int p,int l,int w,int r){
    comp[l][u] = r;
    dis[l][u] = w;
	ind[l][u] = tim[l]++;
    ind[l][u]++;
	ver[l].pb(u);
    int I = mp[Mp(min(u,p),max(u,p))];
    E[I].pb(l);
    for(auto h : g[u]){
        if(h.fi!=p and !mark[h.fi]) dfs(h.fi,u,l,w + h.sec,r);
    }
	ind2[l][u] = tim[l];
    ind2[l][u]++;
}
int dec(int u,int l){
    int c = centroid(u,u,dfs_sz(u,u));
    mark[c] = 1;
    lev[c] = l;
    dis[l][c] = 0;
    ver[l].pb(c);
	ind[l][c] = (tim[l]++);
    ind[l][c]++;
    for(auto h : g[c]){
        if(!mark[h.fi]){
            dfs(h.fi,c,l,h.sec,h.fi);
        }
    }
    ind2[l][c] = tim[l];
    ind2[l][c]++;
    for(auto h : g[c]){
        if(!mark[h.fi]) par[dec(h.fi,l+1)] = c;
    }
    return c;
}
struct node{
    pii mx;
    int lazy=1;
    node(pii a,int l){mx = a,lazy = l;}
    node(){}
};
struct SEG{
    node seg[N<<2];
    node khon = node({-inf,-1},0);
    node merge(const node& a,const node& b){
        return node(max(a.mx,b.mx),0);
    }
    void shift(int u,int l,int r,int x){
        seg[u].mx.fi += x;
        seg[u].lazy += x;
    }
    void relax(int u,int l,int r){
        int mid = (l+r)>>1;
        shift(lid,l,mid,seg[u].lazy);
        shift(rid,mid,r,seg[u].lazy);
        seg[u].lazy = 0;
    }
    void build(int u=1,int l=1,int r=n+1){
        if(r-l==1){
            seg[u].mx = {0,l};
            seg[u].lazy = 0;
            return ;
        }
        int mid = (l+r)>>1;
        build(lid,l,mid);
        build(rid,mid,r);
        seg[u] = merge(seg[lid],seg[rid]);
    }
    void update(int s,int e,int v,int u=1,int l=1,int r=n+1){
        if(e <= l || e <= l || r <= s) return ;
        if(s <= l and r <= e){
            shift(u,l,r,v);
            return ;
        }
        int mid = (l+r)>>1;
        relax(u,l,r);
        update(s,e,v,lid,l,mid);
        update(s,e,v,rid,mid,r);
        seg[u] = merge(seg[lid],seg[rid]);
    }
    node get(int s,int e,int u=1,int l=1,int r=n+1){
        if(e <= s) return khon;
        if(s <= l and r <= e) return seg[u];
        int mid = (l+r)>>1;
        relax(u,l,r);
        if(e <= mid) return get(s,e,lid,l,mid);
        if(s >= mid) return get(s,e,rid,mid,r);
        return merge(get(s,e,lid,l,mid), get(s,e,rid,mid,r));
    }
} se[LOG];
vector<int> wei;
vector<pii> arr;
void change(int j,int w){
    int dif = -wei[j] + w;
    wei[j] = w;
    for(auto h : E[j]){
        int u = arr[j].fi,v= arr[j].sec;
        if(ind[h][u] > ind[h][v]) swap(u,v);
        se[h].update(ind[h][v],ind2[h][v],dif);
    }
}
pii ask(int v){
    pii ans = se[lev[v]].get(ind[lev[v]][v],ind2[lev[v]][v]).mx;
    int u = v;
    int lst = v;
    v = par[v];
    while(v){
        int tmp = se[lev[v]].get(ind[lev[v]][u],ind[lev[v]][u]+1).mx.fi;
        pii tmp2 = max(se[lev[v]].get(ind[lev[v]][v],ind[lev[v]][comp[lev[v]][lst]]).mx,se[lev[v]].get(ind2[lev[v]][comp[lev[v]][lst]],ind2[lev[v]][v]).mx);
        tmp2.fi += tmp;
        tmp2.sec = ver[lev[v]][tmp2.sec - 1];
        ans = max(ans,tmp2);
        lst = v;
        v = par[v];
    }
    return ans;
}
int32_t main() {
	ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0);
    int W ;
	cin >> n >> q >> W;
	for(int i = 0 ; i < n -1;i++){
		int u,v,w;
		cin >> u >> v >> w;
        wei.pb(w);
        arr.pb(Mp(min(u,v),max(u,v)));
        mp[Mp(min(u,v),max(u,v))] = i;
		g[u].pb(Mp(v,w));
		g[v].pb(Mp(u,w));
	}
    dec(1,0);
    for(int i = 0 ; i < LOG;i++) se[i].build();
    for(int i =1 ;i <= n;i++){
        int v = i;
        while(v){
            se[lev[v]].update(ind[lev[v]][i],ind[lev[v]][i]+1,dis[lev[v]][i]);
            v = par[v];
        }
    }
    
    int last = 0;
    while(q--){
        int e,w;
        cin >> e >> w;
        e = (e + last)%(n-1);
        w = (w+last)%W;
        change(e,w);
        last = ask(ask(1).sec).fi;
        cout << last << endl;
    }
    

	
	return 0;
}

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