oj.uz

Submission #540713

# Submission time Handle Problem Language Result Execution time Memory
540713 2022-03-21T13:35:39 Z jamezzz Dynamic Diameter (CEOI19_diameter) C++17
36 / 100
 5000 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
 
#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 2023456789123456789
#define all(x) x.begin(), x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef pair<ll,int> li;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));
 
#define mod 1000000007
 
inline int add(int a,int b){
	int r=a+b;
	while(r>=mod)r-=mod;
	while(r<0)r+=mod;
	return r;
}
 
inline int mult(int a,int b){
	return (int)(((ll)(a*b))%mod);
}
 
inline int rd(){
	int x=0;
	char ch=getchar_unlocked();
	while(!(ch&16))ch=getchar();//keep reading while current character is whitespace
    while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar_unlocked();
	}
	return x;
}
 
#define maxn 100005
 
struct edge{
	int u,v;ll w;
	vector<int> comp;
	vector<ii> range;
};
 
struct node{
	int s,e;ll ans;
	vector<li> v;
	vector<ll> lz;
	vector<ii> ranges;
	
	void init(int i,int l,int r){
		v[i]={0,l};
		lz[i]=0;
		if(l==r)return;
		int m=(l+r)>>1;
		init(2*i+1,l,m);
		init(2*i+2,m+1,r);
	}
	
	node(int _s,int _e){
		s=_s;e=_e;
		v.resize(4*(e-s+1));
		lz.resize(4*(e-s+1),0);
		ranges.resize(e-s+1);
		init(0,s,e);
	}
	
	void ppo(int i,int l,int r){
		v[i].fi+=lz[i];
		if(l!=r){
			lz[2*i+1]+=lz[i];
			lz[2*i+2]+=lz[i];
		}
		lz[i]=0;
	}
	
	void up(int i,int l,int r,int x,int y,ll nv){
		//pf("up: %d %d %d %d %d %lld\n",i,l,r,x,y,nv);
		if(l==x&&r==y){
			lz[i]+=nv;return;
		}
		int m=(l+r)>>1;
		if(y<=m)up(2*i+1,l,m,x,y,nv);
		else if(x>m)up(2*i+2,m+1,r,x,y,nv);
		else{
			up(2*i+1,l,m,x,m,nv);
			up(2*i+2,m+1,r,m+1,y,nv);
		}
		//pf("left child: %lld %d %lld\n",v[2*i+1].fi,v[2*i+1].se,lz[2*i+1]);
		//pf("right child: %lld %d %lld\n",v[2*i+2].fi,v[2*i+2].se,lz[2*i+2]);
		ppo(2*i+1,l,m);ppo(2*i+2,m+1,r);
		//pf("%d %d old val: %lld %d\n",l,r,v[i].fi,v[i].se);
		v[i]=max(v[2*i+1],v[2*i+2]);
		//pf("%d %d new val: %lld %d\n",l,r,v[i].fi,v[i].se);
		//pf("left child: %lld %d\n",v[2*i+1].fi,v[2*i+1].se);
		//pf("right child: %lld %d\n",v[2*i+2].fi,v[2*i+2].se);
	}
	
	void up(int x,int y,ll nv){
		//pf("up: %d %d %lld\n",x,y,nv);
		up(0,s,e,x,y,nv);
	}
	
	void print(int i,int l,int r){
		//pf("node: %d %d %d %lld %d %lld\n",i,l,r,v[i].fi,v[i].se,lz[i]);
		int m=(l+r)>>1;
		if(l!=r)print(2*i+1,l,m),print(2*i+2,m+1,r);
	}
	
	ll qry(){
		//pf("qry:\n");
		ans=v[0].fi+lz[0];
		//pf("%lld %d\n",v[0].fi,v[0].se);
		int i=v[0].se;
		up(ranges[i].fi,ranges[i].se,-LINF);
		//pf("%lld %d\n",v[0].fi,v[0].se);
		if(v[0].fi+lz[0]>=0)ans+=v[0].fi+lz[0];
		up(ranges[i].fi,ranges[i].se,LINF);
		return ans;
	}
	
}*root[maxn];
 
int n,q,sub[maxn];ll w;
bool mark[maxn];
vii AL[maxn];
vector<edge> edges;
 
void find_sz(int u,int p){
	sub[u]=1;
	for(auto[v,i]:AL[u]){
		if(mark[v]||v==p)continue;
		find_sz(v,u);
		sub[u]+=sub[v];
	}
}
 
int cnt;
vii ranges;
 
ii dfs(int u,int p,int c){
	ii range={cnt,cnt};++cnt;
	for(auto[v,i]:AL[u]){
		if(mark[v]||v==p)continue;
		ii res=dfs(v,u,c);
		edges[i].comp.pb(c);
		edges[i].range.pb(res);
		mxto(range.se,res.se);
		if(p==-1)ranges.pb(res);
	}
	return range;
}
 
void decomp(int u){
	find_sz(u,-1);
	int c=u;
	while(true){
		bool val=true;
		for(auto[v,i]:AL[u]){
			if(!mark[v]&&sub[v]<sub[c]&&sub[v]>=sub[u]/2){
				c=v;val=false;break;
			}
		}
		if(val)break;
	}
	
	cnt=0;
	ranges.clear();
	
	dfs(c,-1,c);
	
	root[c]=new node(0,cnt-1);
	
	for(int i=0;i<sz(ranges);++i){
		for(int j=ranges[i].fi;j<=ranges[i].se;++j){
			root[c]->ranges[j]=ranges[i];
		}
	}
	
	mark[c]=true;
	for(auto[v,i]:AL[c]){
		if(!mark[v])decomp(v);
	}
}
 
int main(){
	sf("%d%d%lld",&n,&q,&w);
	for(int i=0;i<n-1;++i){
		int a,b;ll c;
		sf("%d%d%lld",&a,&b,&c);
		AL[a].pb({b,i});
		AL[b].pb({a,i});
		edges.pb({a,b,c,{},{}});
	}
	
	decomp(1);
	
	for(edge &e:edges){
		for(int i=0;i<sz(e.comp);++i){
			ii rng=e.range[i];
			//root[e.comp[i]]->print(0,root[e.comp[i]]->s,root[e.comp[i]]->e);
			root[e.comp[i]]->up(rng.fi,rng.se,e.w);
			//root[e.comp[i]]->print(0,root[e.comp[i]]->s,root[e.comp[i]]->e);
		}
	}
	
	set<li> s;
	for(int i=1;i<=n;++i){
		s.insert({root[i]->qry(),i});
		//pf("init: %lld %d\n",root[i]->qry(),i);
	}
	
	//pf("-------------start--------------\n");
	ll ans=0;
	while(q--){
		ll idx,nw;
		sf("%lld%lld",&idx,&nw);
		idx=(idx+ans)%(n-1);
		nw=(nw+ans)%w;
		edge &e=edges[idx];
		ll ow=e.w;
		e.w=nw;
		
		//dbg("upd: %d %lld\n",idx,nw);
		
		for(int i=0;i<sz(e.comp);++i){
			ii rng=e.range[i];
			int c=e.comp[i];
			
			ll old=root[c]->ans;
			root[c]->up(rng.fi,rng.se,nw-ow);
			ll upd=root[c]->qry();
			s.erase(s.find({old,c}));
			s.insert({upd,c});
		}
		
		ans=(*--s.end()).fi;
		
		pf("%lld\n",ans);
	}
}

Compilation message

diameter.cpp: In function 'int main()':
diameter.cpp:208:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  208 |  sf("%d%d%lld",&n,&q,&w);
      |    ^
diameter.cpp:211:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  211 |   sf("%d%d%lld",&a,&b,&c);
      |     ^
diameter.cpp:238:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  238 |   sf("%lld%lld",&idx,&nw);
      |     ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2772 KB Output is correct
16 Correct 2 ms 2772 KB Output is correct
17 Correct 2 ms 2772 KB Output is correct
18 Correct 4 ms 2772 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2772 KB Output is correct
16 Correct 2 ms 2772 KB Output is correct
17 Correct 2 ms 2772 KB Output is correct
18 Correct 4 ms 2772 KB Output is correct
19 Correct 44 ms 4136 KB Output is correct
20 Correct 77 ms 4892 KB Output is correct
21 Correct 268 ms 8520 KB Output is correct
22 Correct 641 ms 18720 KB Output is correct
23 Correct 85 ms 10716 KB Output is correct
24 Correct 460 ms 31184 KB Output is correct
25 Correct 1801 ms 96736 KB Output is correct
26 Execution timed out 5133 ms 726852 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 12 ms 2776 KB Output is correct
5 Correct 57 ms 2988 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2900 KB Output is correct
8 Correct 2 ms 2900 KB Output is correct
9 Correct 4 ms 2900 KB Output is correct
10 Correct 20 ms 3060 KB Output is correct
11 Correct 87 ms 3388 KB Output is correct
12 Correct 8 ms 5580 KB Output is correct
13 Correct 7 ms 5632 KB Output is correct
14 Correct 10 ms 5692 KB Output is correct
15 Correct 33 ms 5744 KB Output is correct
16 Correct 133 ms 6220 KB Output is correct
17 Correct 136 ms 62532 KB Output is correct
18 Correct 139 ms 62640 KB Output is correct
19 Correct 136 ms 62724 KB Output is correct
20 Correct 175 ms 62836 KB Output is correct
21 Correct 332 ms 63224 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3796 KB Output is correct
2 Correct 39 ms 3900 KB Output is correct
3 Correct 189 ms 4112 KB Output is correct
4 Correct 354 ms 4452 KB Output is correct
5 Correct 50 ms 17472 KB Output is correct
6 Correct 109 ms 17604 KB Output is correct
7 Correct 368 ms 17896 KB Output is correct
8 Correct 712 ms 18212 KB Output is correct
9 Correct 270 ms 87636 KB Output is correct
10 Correct 354 ms 87728 KB Output is correct
11 Correct 771 ms 87892 KB Output is correct
12 Correct 1285 ms 88332 KB Output is correct
13 Correct 549 ms 179992 KB Output is correct
14 Correct 666 ms 180008 KB Output is correct
15 Correct 1153 ms 180468 KB Output is correct
16 Correct 1771 ms 180568 KB Output is correct
17 Correct 2506 ms 180576 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 2969 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2772 KB Output is correct
16 Correct 2 ms 2772 KB Output is correct
17 Correct 2 ms 2772 KB Output is correct
18 Correct 4 ms 2772 KB Output is correct
19 Correct 44 ms 4136 KB Output is correct
20 Correct 77 ms 4892 KB Output is correct
21 Correct 268 ms 8520 KB Output is correct
22 Correct 641 ms 18720 KB Output is correct
23 Correct 85 ms 10716 KB Output is correct
24 Correct 460 ms 31184 KB Output is correct
25 Correct 1801 ms 96736 KB Output is correct
26 Execution timed out 5133 ms 726852 KB Time limit exceeded
27 Halted 0 ms 0 KB -