답안 #251989

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
251989	2020-07-23T13:21:02 Z	errorgorn	Dynamic Diameter (CEOI19_diameter)	C++14	7 / 100	3839 ms	46188 KB

diameter

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

struct node{
	int s,e,m;
	ii val;
	ll lazy=0;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		val=ii(0,s);
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void propo(){
		if (lazy){
			val.fi+=lazy;
			
			if (s!=e){
				l->lazy+=lazy;
				r->lazy+=lazy;
			}
			
			lazy=0;
		}
	}
	
	void update(int i,int j,ll k){
		if (s==i && e==j) lazy+=k;
		else{
			if (j<=m) l->update(i,j,k);
			else if (m<i) r->update(i,j,k);
			else l->update(i,m,k),r->update(m+1,j,k);
			
			l->propo(),r->propo();
			val=max(l->val,r->val);
		}
	}
	
	ii query(int i,int j){
		propo();
		
		if (s==i && e==j) return val;
		else if (j<=m) return l->query(i,j);
		else if (m<i) return r->query(i,j);
		else return max(l->query(i,m),r->query(m+1,j));
	}
} *root=new node(0,100005);

ll n,q,w;
vector<ii> al[100005];
ll cw[100005];
ii range[100005];
ii subtree[100005];

int TIME=1;
ii dfs(int i,int p){
	ii r=ii(1e9,-1e9);
	
	for (auto &it:al[i]){
		if (it.fi==p) continue;
		
		auto temp=dfs(it.fi,i);
		
		if (i==1){
			rep(x,temp.fi,temp.se+1) subtree[x]=temp;
		}
		
		range[it.se]=temp;
		r.fi=min(r.fi,temp.fi);
		r.se=max(r.se,temp.se);
	}
	
	if (r==ii(1e9,-1e9)){
		r=ii(TIME,TIME);
		TIME++;
	}
	
	return r;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>q>>w;
	
	int a,b,c;
	rep(x,0,n-1){
		cin>>a>>b>>c;
		
		al[a].push_back(ii(b,x));
		al[b].push_back(ii(a,x));
		cw[x]=c;
	}
	
	dfs(1,-1);
	
	rep(x,0,n-1){
		//cout<<range[x].fi<<" "<<range[x].se<<endl;
		root->update(range[x].fi,range[x].se,cw[x]);
	}
	
	ll last=0;
	ll d,e;
	while (q--){
		cin>>d>>e;
		
		d=(d+last)%(n-1);
		e=(e+last)%w;
		
		//cout<<d<<" "<<e<<endl;
		
		root->update(range[d].fi,range[d].se,e-cw[d]);
		cw[d]=e;
		
		auto temp=root->query(0,100005);
		last=temp.fi+max(root->query(0,subtree[temp.se].fi-1),root->query(subtree[temp.se].se+1,100005)).fi;
		
		cout<<last<<endl;
	}
}

Compilation message

diameter.cpp: In constructor 'node::node(int, int)':
diameter.cpp:41:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   s=_s,e=_e,m=s+e>>1;
               ~^~

Subtask #1
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	13 ms	15232 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	13 ms	15232 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	15240 KB	Output is correct
2	Correct	13 ms	15232 KB	Output is correct
3	Correct	20 ms	15232 KB	Output is correct
4	Correct	25 ms	15480 KB	Output is correct
5	Correct	74 ms	16376 KB	Output is correct
6	Correct	13 ms	15232 KB	Output is correct
7	Correct	12 ms	15232 KB	Output is correct
8	Correct	12 ms	15360 KB	Output is correct
9	Correct	14 ms	15360 KB	Output is correct
10	Correct	27 ms	15612 KB	Output is correct
11	Correct	83 ms	16632 KB	Output is correct
12	Correct	16 ms	15736 KB	Output is correct
13	Correct	16 ms	15756 KB	Output is correct
14	Correct	16 ms	15744 KB	Output is correct
15	Correct	44 ms	16120 KB	Output is correct
16	Correct	95 ms	17300 KB	Output is correct
17	Correct	67 ms	25064 KB	Output is correct
18	Correct	66 ms	25064 KB	Output is correct
19	Correct	69 ms	25100 KB	Output is correct
20	Correct	89 ms	25316 KB	Output is correct
21	Correct	189 ms	26636 KB	Output is correct