oj.uz

Submission #252003

# Submission time Handle Problem Language Result Execution time Memory
252003 2020-07-23T14:55:21 Z errorgorn Dynamic Diameter (CEOI19_diameter) C++14
7 / 100
 2012 ms 385544 KB 
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#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));
	}
};

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

bool used[100005];
int ss[100005];

void dfs_c(int i,int p){
	ss[i]=1;

	for (auto &it:al[i]){
		if (it.fi==p || used[it.fi]) continue;
		
		dfs_c(it.fi,i);
		ss[i]+=ss[it.fi];
	}
}

ll cw[100005];
unordered_map<int,ii> range[100005];
vector<ii> subtree[100005];
vector<int> pos[100005];
node* root[100005];

ll ans[100005];
bool degen[100005];

int TIME;
ii dfs(int i,int p,int root){
	ii r=ii(1e9,-1e9);
	
	for (auto &it:al[i]){
		if (it.fi==p || used[it.fi]) continue;
		
		auto temp=dfs(it.fi,i,root);
		
		if (i==root){
			rep(x,temp.fi,temp.se+1) subtree[root].push_back(temp);
		}
		
		range[root][it.se]=temp;
		pos[it.se].push_back(root);
		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;
}

void centroid(int i,int sz){
	//cout<<i<<" "<<sz<<endl;

	dfs_c(i,-1);
	
	int p=-1;
	reloop:
	for (auto &it:al[i]){
		if (it.fi==p || used[it.fi]) continue;
		
		if (ss[it.fi]>sz/2){
			p=i;
			i=it.fi;
			goto reloop;
		}
	}
	
	if (sz==1){
		degen[i]=true;
	}
	else{
		TIME=1;
		subtree[i].push_back(ii(0,0));
		root[i]=new node(0,dfs(i,-1,i).se+1);
	}
	
	used[i]=true;
	
	sz--;
	for (auto &it:al[i]){
		if (it.fi==p || used[it.fi]) continue;
		
		centroid(it.fi,ss[it.fi]);
		sz-=ss[it.fi];
	}
	
	if (p!=-1) centroid(p,sz);
}

ll get(int i){
	if (degen[i]) return 0;

	auto temp=root[i]->query(root[i]->s,root[i]->e);
	return temp.fi+max(root[i]->query(root[i]->s,subtree[i][temp.se].fi-1),root[i]->query(subtree[i][temp.se].se+1,root[i]->e)).fi;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>q>>w;
	
	ll 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;
	}
	
	centroid(1,n);
	
	rep(x,0,n-1){
		for (auto &it:pos[x]){
			root[it]->update(range[it][x].fi,range[it][x].se,cw[x]);
		}
	}
	
	multiset<ll> s;
	
	rep(x,1,n+1){
		ans[x]=get(x);
		//cout<<x<<" "<<ans[x]<<endl;
		s.insert(ans[x]);
	}
	
	ll last=0;
	ll d,e;
	while (q--){
		cin>>d>>e;
		
		d=(d+last)%(n-1);
		e=(e+last)%w;
		
		for (auto &it:pos[d]){
			s.erase(s.find(ans[it]));
			
			root[it]->update(range[it][d].fi,range[it][d].se,e-cw[d]);
			
			ans[it]=get(it);
			s.insert(ans[it]);
		}
		cw[d]=e;
		
		last=*s.rbegin();
		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

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 25856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 25856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12928 KB Output is correct
2 Correct 8 ms 12928 KB Output is correct
3 Correct 9 ms 12928 KB Output is correct
4 Correct 19 ms 13056 KB Output is correct
5 Correct 60 ms 13372 KB Output is correct
6 Correct 8 ms 12928 KB Output is correct
7 Correct 8 ms 13056 KB Output is correct
8 Correct 8 ms 13056 KB Output is correct
9 Correct 10 ms 13056 KB Output is correct
10 Correct 25 ms 13184 KB Output is correct
11 Correct 84 ms 13608 KB Output is correct
12 Correct 14 ms 14592 KB Output is correct
13 Correct 14 ms 14592 KB Output is correct
14 Correct 15 ms 14592 KB Output is correct
15 Correct 34 ms 14720 KB Output is correct
16 Correct 112 ms 15232 KB Output is correct
17 Correct 120 ms 47204 KB Output is correct
18 Correct 118 ms 47204 KB Output is correct
19 Correct 114 ms 47204 KB Output is correct
20 Correct 144 ms 47332 KB Output is correct
21 Correct 293 ms 47972 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14208 KB Output is correct
2 Correct 42 ms 14328 KB Output is correct
3 Correct 154 ms 14496 KB Output is correct
4 Correct 314 ms 14840 KB Output is correct
5 Runtime error 103 ms 61304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 2012 ms 385544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 25856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -