Submission #1099588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099588		StefanSebez	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	3217 ms	352116 KiB

diameter

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
vector<int>Unique(vector<int>a){sort(a.begin(),a.end());int m=unique(a.begin(),a.end())-a.begin();a.resize(m);return a;}
const int N=1e5+50;
vector<array<ll,3>>E[N];
vector<pair<int,int>>edges;
vector<int>mapa[N];
ll weights[N],res;
multiset<ll>st;
bool was[N];
struct Node{ll maks;int i;};
Node Merge(Node a,Node b){return a.maks>=b.maks?a:b;}
struct SegTree{
	int nc,root;vector<int>lc,rc;vector<Node>node;vector<ll>lazy;
	SegTree(){}
	SegTree(int n){lc.assign(2*n+50,0),rc.assign(2*n+50,0),node.assign(2*n+50,{0,0}),lazy.assign(2*n+50,0);nc=root=0;Build(root,1,n);}
	void Build(int &c,int ss,int se){
		c=++nc;if(ss==se){node[c]={0,ss};return;}
		int mid=ss+se>>1;Build(lc[c],ss,mid),Build(rc[c],mid+1,se);
		node[c]=Merge(node[lc[c]],node[rc[c]]);
	}
	//inline void update(int c,ll qval){node[c].maks+=qval,lazy[c]+=qval;}
	//inline void push(int c){update(lc[c],lazy[c]),update(rc[c],lazy[c]),lazy[c]=0;}
	void Update(int c,int ss,int se,int qs,int qe,ll qval){
		//if(qs<=ss&&se<=qe){update(c,qval);return;}
		if(qs<=ss&&se<=qe){node[c].maks+=qval,lazy[c]+=qval;return;}
		if(qe<ss||se<qs)return;
		int mid=ss+se>>1;//push(c);
		node[lc[c]].maks+=lazy[c],lazy[lc[c]]+=lazy[c];
		node[rc[c]].maks+=lazy[c],lazy[rc[c]]+=lazy[c];
		lazy[c]=0;
		if(qe<ss||mid<qs) Update(rc[c],mid+1,se,qs,qe,qval);
		else if(qe<mid+1||se<qs) Update(lc[c],ss,mid,qs,qe,qval);
		else Update(lc[c],ss,mid,qs,qe,qval),Update(rc[c],mid+1,se,qs,qe,qval);
		node[c]=Merge(node[lc[c]],node[rc[c]]);
	}
	Node Get(int c,int ss,int se,int qs,int qe){
		if(qs>qe||qe<ss||se<qs)return {0,0};
		if(qs<=ss&&se<=qe)return node[c];
		int mid=ss+se>>1;//push(c);
		node[lc[c]].maks+=lazy[c],lazy[lc[c]]+=lazy[c];
		node[rc[c]].maks+=lazy[c],lazy[rc[c]]+=lazy[c];
		lazy[c]=0;
		if(qe<ss||mid<qs) return Get(rc[c],mid+1,se,qs,qe);
		if(qe<mid+1||se<qs) return Get(lc[c],ss,mid,qs,qe);
		return Merge(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
	}
};
struct CentroidTreeNode{
	int nc;vector<int>roots,in,out,Vals;SegTree ST;
	CentroidTreeNode(){}
	CentroidTreeNode(int n,int rt){roots.assign(n+50,0),in.assign(n+50,0),out.assign(n+50,0);nc=0;DFSprecalc(rt,0);Vals=Unique(Vals);DFSCalc(rt,0);Calcroots(rt);ST=SegTree(nc);}
	int ind(int x){return lower_bound(Vals.begin(),Vals.end(),x)-Vals.begin();}
	void DFSprecalc(int u,int parent){Vals.pb(u);for(auto i:E[u]) if(!was[i[0]]&&i[0]!=parent) DFSprecalc(i[0],u);}
	void DFSCalc(int u,int parent){
		int num=0,idx=ind(u);
		for(auto i:E[u]){
			if(was[i[0]]||i[0]==parent) continue;
			DFSCalc(i[0],u);
			num++;if(num==1) in[idx]=in[ind(i[0])];
		}
		if(!num) in[idx]=++nc;
		out[idx]=nc;
	}
	void Calcroots(int u){for(auto i:E[u]) if(!was[i[0]]) DFSroots(i[0],u,i[0]);}
	void DFSroots(int u,int parent,int prvi){
		roots[in[ind(u)]]=prvi;
		for(auto i:E[u]) if(!was[i[0]]&&i[0]!=parent) DFSroots(i[0],u,prvi);
	}
	ll GetMax(){
		Node x=ST.Get(1,1,nc,1,nc);
		int u=roots[x.i],idx=ind(u);
		Node y=Merge(ST.Get(1,1,nc,1,in[idx]-1),ST.Get(1,1,nc,out[idx]+1,nc));
		return x.maks+y.maks;
	}
	void Update(int u,int v,ll w){
		st.erase(st.find(GetMax()));
		int ind1=ind(u),ind2=ind(v);
		if(out[ind1]-in[ind1]>out[ind2]-in[ind2]) swap(u,v),swap(ind1,ind2);
		ST.Update(1,1,nc,in[ind1],out[ind1],w);
		st.insert(GetMax());
	}
}cnode[N];
int sajz[N],nc;
void DFSCalc(int u,int parent){
	sajz[u]=1;
	for(auto i:E[u]) if(!was[i[0]]&&i[0]!=parent){DFSCalc(i[0],u);sajz[u]+=sajz[i[0]];}
}
int DFSC(int u,int parent,int sz){
	for(auto i:E[u]){if(!was[i[0]]&&i[0]!=parent&&sajz[i[0]]*2>=sz) return DFSC(i[0],u,sz);}
	return u;
}
void DFS1(int u,int parent,int ct,ll depth){
	int num=0;
	for(auto i:E[u]){
		if(was[i[0]]||i[0]==parent) continue;
		DFS1(i[0],u,ct,depth+i[1]);num++;
		mapa[i[2]].pb(ct);
	}
	if(!num){int idx=cnode[ct].ind(u);cnode[ct].ST.Update(cnode[ct].ST.root,1,cnode[ct].nc,cnode[ct].in[idx],cnode[ct].in[idx],depth);}
}
void CD(int u){
	DFSCalc(u,0);int sz=sajz[u];u=DFSC(u,0,sz);
	cnode[++nc]=CentroidTreeNode(sz,u);DFS1(u,0,nc,0);
	was[u]=true;for(auto i:E[u]) if(!was[i[0]]) CD(i[0]);
}
int main(){
    int n,q;ll WW;scanf("%i%i%lld",&n,&q,&WW);
    for(int i=0;i<n-1;i++){
		int u,v;ll w;scanf("%i%i%lld",&u,&v,&w);
		E[u].pb({v,w,i}),E[v].pb({u,w,i});edges.pb({u,v});weights[i]=w;
    }
    for(int i=0;i<=n;i++) mapa[i].reserve(21);
    CD(1);for(int i=1;i<=n;i++) st.insert(cnode[i].GetMax());
    while(q--){
		ll ind,w;scanf("%lld%lld",&ind,&w);ind=(ind+res)%(n-1);w=(w+res)%WW;
		int u=edges[ind].fi,v=edges[ind].se;w-=weights[ind];
		for(auto i:mapa[ind]) cnode[i].Update(u,v,w);
		weights[ind]+=w;res=*st.rbegin();printf("%lld\n",res);
    }
    return 0;
}

Compilation message (stderr)

diameter.cpp: In member function 'void SegTree::Build(int&, int, int)':
diameter.cpp:24:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |   int mid=ss+se>>1;Build(lc[c],ss,mid),Build(rc[c],mid+1,se);
      |             ^
diameter.cpp: In member function 'void SegTree::Update(int, int, int, int, int, long long int)':
diameter.cpp:33:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |   int mid=ss+se>>1;//push(c);
      |             ^
diameter.cpp: In member function 'Node SegTree::Get(int, int, int, int, int)':
diameter.cpp:45:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |   int mid=ss+se>>1;//push(c);
      |             ^
diameter.cpp: In function 'int main()':
diameter.cpp:113:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |     int n,q;ll WW;scanf("%i%i%lld",&n,&q,&WW);
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:115:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |   int u,v;ll w;scanf("%i%i%lld",&u,&v,&w);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~
diameter.cpp:121:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |   ll ind,w;scanf("%lld%lld",&ind,&w);ind=(ind+res)%(n-1);w=(w+res)%WW;
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~

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