Submission #1095417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095417		PieArmy	Dynamic Diameter (CEOI19_diameter)	C++17	49 / 100	5040 ms	431008 KiB

diameter

typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}
 
struct Seg{
	int n;
	vector<ll>sum,pref,suf,mx,arr;
	void build(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			sum[node]=arr[left];
			mx[node]=pref[node]=suf[node]=max(arr[left],0ll);
			return;
		}
		build(node+1,left,mid);build(node+((mid-left+1)<<1),mid+1,right);
		sum[node]=sum[node+1]+sum[node+((mid-left+1)<<1)];
		pref[node]=max(pref[node+1],sum[node+1]+pref[node+((mid-left+1)<<1)]);
		suf[node]=max(suf[node+((mid-left+1)<<1)],sum[node+((mid-left+1)<<1)]+suf[node+1]);
		mx[node]=max(max(mx[node+1],mx[node+((mid-left+1)<<1)]),pref[node+((mid-left+1)<<1)]+suf[node+1]);
	}
	void yap(vector<ll>A){
		arr=A;
		n=arr.size();
		sum.resize((n<<1)+1);
		pref.resize((n<<1)+1);
		suf.resize((n<<1)+1);
		mx.resize((n<<1)+1);
		build();
	}
	int tar;ll x;
	void up(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			sum[node]=x;
			mx[node]=pref[node]=suf[node]=max(x,0ll);
			return;
		}
		if(tar>mid)up(node+((mid-left+1)<<1),mid+1,right);
		else up(node+1,left,mid);
		sum[node]=sum[node+1]+sum[node+((mid-left+1)<<1)];
		pref[node]=max(pref[node+1],sum[node+1]+pref[node+((mid-left+1)<<1)]);
		suf[node]=max(suf[node+((mid-left+1)<<1)],sum[node+((mid-left+1)<<1)]+suf[node+1]);
		mx[node]=max(max(mx[node+1],mx[node+((mid-left+1)<<1)]),pref[node+((mid-left+1)<<1)]+suf[node+1]);
	}
	void update(int a,ll b){
		tar=a;x=b;
		up();
	}
};
 
int n,q;
ll w;
vector<pair<int,ll>>adj[100001];
map<int,pair<int,int>>in_out[100001];
map<int,int>dep[100001];
multiset<ll>vals[100001];
vector<Seg>seg[100001];
int level[100001],par[100001],parnum[100001];
pair<int,int>edge[100001];
multiset<ll>bests;
// temp stuff
int sub[100001];
// temp stuff
 
void dfs1(int pos,int prev){
	sub[pos]=1;
	for(auto[x,y]:adj[pos]){
		if(level[x]==0&&x!=prev){
			dfs1(x,pos);
			sub[pos]+=sub[x];
		}
	}
}
 
void dfs2(int pos,int prev,int root,ll l,vector<ll>&v){
	in_out[root][pos].fr=v.size();
	v.pb(l);
	for(auto[x,y]:adj[pos]){
		if(level[x])continue;
		if(x==prev)continue;
		dep[root][x]=dep[root][pos]+1;
		dfs2(x,pos,root,y,v);
	}
	in_out[root][pos].sc=v.size();
	v.pb(-l);
}
 
void cal(int pos,int prev,int num){
	dfs1(pos,0);
	int total=sub[pos];
	int paren=pos;
	while(true){
		int nex=0;
		for(auto[x,y]:adj[pos]){
			if(level[x]!=0||x==paren)continue;
			if(sub[x]>=(total>>1)){
				nex=x;
				break;
			}
		}
		if(!nex)break;
		paren=pos;
		pos=nex;
	}
	par[pos]=prev;
	parnum[pos]=num;
	level[pos]=level[par[pos]]+1;
	seg[pos].resize(adj[pos].size());
	vals[pos].insert(0);
	vals[pos].insert(0);
	for(int i=0;i<adj[pos].size();i++){
		if(level[adj[pos][i].fr])continue;
		vector<ll>v;
		dep[pos][adj[pos][i].fr]=1;
		dfs2(adj[pos][i].fr,pos,pos,adj[pos][i].sc,v);
		seg[pos][i].yap(v);
		vals[pos].insert(seg[pos][i].mx[1]);
	}
	ll topla=0;
	auto itr=vals[pos].end();
	itr--;
	topla+=*itr;
	itr--;
	topla+=*itr;
	bests.insert(topla);
	for(int i=0;i<adj[pos].size();i++){
		if(level[adj[pos][i].fr])continue;
		cal(adj[pos][i].fr,pos,i);
	}
}
 
void code(){
	cin>>n>>q>>w;
	for(int i=0;i<n-1;i++){
		int a,b;ll c;
		cin>>a>>b>>c;
		edge[i]={a,b};
		adj[a].pb({b,c});
		adj[b].pb({a,c});
	}
	cal(1,0,0);
	ll ans=0;
	while(q--){
		int d;ll e;
		cin>>d>>e;
		d=(d+ans)%(n-1);
		e=(e+ans)%w;
		if(level[edge[d].fr]>level[edge[d].sc])swap(edge[d].fr,edge[d].sc);
		int pos=edge[d].fr;
		int sira;
		int pos2=edge[d].sc;
		while(pos2!=pos){
			sira=parnum[pos2];
			pos2=par[pos2];
		}
		while(pos){
			ll topla=0;
			auto itr=vals[pos].end();
			itr--;topla+=*itr;itr--;topla+=*itr;
			bests.erase(bests.find(topla));
			vals[pos].erase(vals[pos].find(seg[pos][sira].mx[1]));
			int cur=edge[d].fr;
			if(dep[pos][cur]<dep[pos][edge[d].sc])cur=edge[d].sc;
			seg[pos][sira].update(in_out[pos][cur].fr,e);
			seg[pos][sira].update(in_out[pos][cur].sc,-e);
			vals[pos].insert(seg[pos][sira].mx[1]);
			topla=0;
			itr=vals[pos].end();
			itr--;topla+=*itr;itr--;topla+=*itr;
			bests.insert(topla);
			sira=parnum[pos];
			pos=par[pos];
		}
		ans=*(--bests.end());
		cout<<ans<<endl;
	}
}
 
int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
	int t=1;
	if(!t)cin>>t;
	while(t--){code();}
	return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'void cal(int, int, int)':
diameter.cpp:120:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |  for(int i=0;i<adj[pos].size();i++){
      |              ~^~~~~~~~~~~~~~~~
diameter.cpp:135:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |  for(int i=0;i<adj[pos].size();i++){
      |              ~^~~~~~~~~~~~~~~~
diameter.cpp: In function 'int main()':
diameter.cpp:190:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  190 |  bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~
diameter.cpp:190:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  190 |  bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~
diameter.cpp: In function 'void code()':
diameter.cpp:170:48: warning: 'sira' may be used uninitialized in this function [-Wmaybe-uninitialized]
  170 |    vals[pos].erase(vals[pos].find(seg[pos][sira].mx[1]));
      |                                                ^

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