oj.uz

Submission #540712

# Submission time Handle Problem Language Result Execution time Memory
540712 2022-03-21T13:32:13 Z jamezzz Dynamic Diameter (CEOI19_diameter) C++17
100 / 100
 4045 ms 229308 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){
		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);
		}
		ppo(2*i+1,l,m);ppo(2*i+2,m+1,r);
		v[i]=max(v[2*i+1],v[2*i+2]);
	}
	
	void up(int x,int y,ll nv){
		up(0,s,e,x,y,nv);
	}
	
	void print(int i,int l,int r){
		int m=(l+r)>>1;
		if(l!=r)print(2*i+1,l,m),print(2*i+2,m+1,r);
	}
	
	ll qry(){
		ans=v[0].fi+lz[0];
		int i=v[0].se;
		up(ranges[i].fi,ranges[i].se,-LINF);
		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;

vector<int> nodes;

void find_sz(int u,int p){
	nodes.pb(u);
	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){
	nodes.clear();
	find_sz(u,-1);
	int c=u;
	for(int x:nodes){
		int big=sub[u]-sub[x];
		for(auto[v,i]:AL[x]){
			if(mark[v])continue;
			if(sub[v]<sub[x])mxto(big,sub[v]);
		}
		if(2*big<=sub[u]){
			c=x;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]]->up(rng.fi,rng.se,e.w);
		}
	}
	
	set<li> s;
	for(int i=1;i<=n;++i){
		s.insert({root[i]->qry(),i});
	}
	
	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;
		
		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:201:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  201 |  sf("%d%d%lld",&n,&q,&w);
      |    ^
diameter.cpp:204:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  204 |   sf("%d%d%lld",&a,&b,&c);
      |     ^
diameter.cpp:227:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  227 |   sf("%lld%lld",&idx,&nw);
      |     ^

Subtask #1
11.0 / 11.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 2 ms 2644 KB Output is correct
4 Correct 2 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 2664 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 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2664 KB Output is correct

Subtask #2
13.0 / 13.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 2 ms 2644 KB Output is correct
4 Correct 2 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 2664 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 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2664 KB Output is correct
19 Correct 26 ms 3700 KB Output is correct
20 Correct 24 ms 3796 KB Output is correct
21 Correct 31 ms 3976 KB Output is correct
22 Correct 28 ms 4200 KB Output is correct
23 Correct 53 ms 8496 KB Output is correct
24 Correct 64 ms 9720 KB Output is correct
25 Correct 75 ms 10436 KB Output is correct
26 Correct 72 ms 11716 KB Output is correct

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 2664 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 14 ms 2800 KB Output is correct
5 Correct 60 ms 3356 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 3188 KB Output is correct
11 Correct 88 ms 3624 KB Output is correct
12 Correct 8 ms 5708 KB Output is correct
13 Correct 9 ms 5728 KB Output is correct
14 Correct 10 ms 5708 KB Output is correct
15 Correct 35 ms 6024 KB Output is correct
16 Correct 133 ms 6400 KB Output is correct
17 Correct 131 ms 63316 KB Output is correct
18 Correct 134 ms 63360 KB Output is correct
19 Correct 136 ms 63444 KB Output is correct
20 Correct 170 ms 63660 KB Output is correct
21 Correct 321 ms 64508 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3924 KB Output is correct
2 Correct 40 ms 4040 KB Output is correct
3 Correct 177 ms 4368 KB Output is correct
4 Correct 339 ms 4764 KB Output is correct
5 Correct 54 ms 19744 KB Output is correct
6 Correct 109 ms 19820 KB Output is correct
7 Correct 346 ms 20056 KB Output is correct
8 Correct 659 ms 20500 KB Output is correct
9 Correct 294 ms 99908 KB Output is correct
10 Correct 375 ms 100028 KB Output is correct
11 Correct 793 ms 100552 KB Output is correct
12 Correct 1225 ms 100816 KB Output is correct
13 Correct 661 ms 207604 KB Output is correct
14 Correct 726 ms 207520 KB Output is correct
15 Correct 1190 ms 208100 KB Output is correct
16 Correct 1846 ms 208588 KB Output is correct
17 Correct 2674 ms 208368 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2911 ms 170908 KB Output is correct
2 Correct 3077 ms 175668 KB Output is correct
3 Correct 2987 ms 174348 KB Output is correct
4 Correct 2980 ms 175464 KB Output is correct
5 Correct 2924 ms 167280 KB Output is correct
6 Correct 2544 ms 124232 KB Output is correct
7 Correct 4045 ms 212600 KB Output is correct
8 Correct 4003 ms 212400 KB Output is correct
9 Correct 3886 ms 212572 KB Output is correct
10 Correct 3920 ms 211852 KB Output is correct
11 Correct 3820 ms 201780 KB Output is correct
12 Correct 3180 ms 144292 KB Output is correct
13 Correct 3657 ms 229300 KB Output is correct
14 Correct 3426 ms 229264 KB Output is correct
15 Correct 3573 ms 229164 KB Output is correct
16 Correct 3646 ms 228312 KB Output is correct
17 Correct 3350 ms 216028 KB Output is correct
18 Correct 2840 ms 149732 KB Output is correct
19 Correct 3518 ms 229308 KB Output is correct
20 Correct 3520 ms 229036 KB Output is correct
21 Correct 3635 ms 229140 KB Output is correct
22 Correct 3461 ms 228100 KB Output is correct
23 Correct 3400 ms 216140 KB Output is correct
24 Correct 2806 ms 149796 KB Output is correct

Subtask #6
27.0 / 27.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 2 ms 2644 KB Output is correct
4 Correct 2 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 2664 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 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 2 ms 2664 KB Output is correct
19 Correct 26 ms 3700 KB Output is correct
20 Correct 24 ms 3796 KB Output is correct
21 Correct 31 ms 3976 KB Output is correct
22 Correct 28 ms 4200 KB Output is correct
23 Correct 53 ms 8496 KB Output is correct
24 Correct 64 ms 9720 KB Output is correct
25 Correct 75 ms 10436 KB Output is correct
26 Correct 72 ms 11716 KB Output is correct
27 Correct 2 ms 2644 KB Output is correct
28 Correct 2 ms 2664 KB Output is correct
29 Correct 3 ms 2644 KB Output is correct
30 Correct 14 ms 2800 KB Output is correct
31 Correct 60 ms 3356 KB Output is correct
32 Correct 2 ms 2644 KB Output is correct
33 Correct 2 ms 2900 KB Output is correct
34 Correct 2 ms 2900 KB Output is correct
35 Correct 4 ms 2900 KB Output is correct
36 Correct 20 ms 3188 KB Output is correct
37 Correct 88 ms 3624 KB Output is correct
38 Correct 8 ms 5708 KB Output is correct
39 Correct 9 ms 5728 KB Output is correct
40 Correct 10 ms 5708 KB Output is correct
41 Correct 35 ms 6024 KB Output is correct
42 Correct 133 ms 6400 KB Output is correct
43 Correct 131 ms 63316 KB Output is correct
44 Correct 134 ms 63360 KB Output is correct
45 Correct 136 ms 63444 KB Output is correct
46 Correct 170 ms 63660 KB Output is correct
47 Correct 321 ms 64508 KB Output is correct
48 Correct 7 ms 3924 KB Output is correct
49 Correct 40 ms 4040 KB Output is correct
50 Correct 177 ms 4368 KB Output is correct
51 Correct 339 ms 4764 KB Output is correct
52 Correct 54 ms 19744 KB Output is correct
53 Correct 109 ms 19820 KB Output is correct
54 Correct 346 ms 20056 KB Output is correct
55 Correct 659 ms 20500 KB Output is correct
56 Correct 294 ms 99908 KB Output is correct
57 Correct 375 ms 100028 KB Output is correct
58 Correct 793 ms 100552 KB Output is correct
59 Correct 1225 ms 100816 KB Output is correct
60 Correct 661 ms 207604 KB Output is correct
61 Correct 726 ms 207520 KB Output is correct
62 Correct 1190 ms 208100 KB Output is correct
63 Correct 1846 ms 208588 KB Output is correct
64 Correct 2674 ms 208368 KB Output is correct
65 Correct 2911 ms 170908 KB Output is correct
66 Correct 3077 ms 175668 KB Output is correct
67 Correct 2987 ms 174348 KB Output is correct
68 Correct 2980 ms 175464 KB Output is correct
69 Correct 2924 ms 167280 KB Output is correct
70 Correct 2544 ms 124232 KB Output is correct
71 Correct 4045 ms 212600 KB Output is correct
72 Correct 4003 ms 212400 KB Output is correct
73 Correct 3886 ms 212572 KB Output is correct
74 Correct 3920 ms 211852 KB Output is correct
75 Correct 3820 ms 201780 KB Output is correct
76 Correct 3180 ms 144292 KB Output is correct
77 Correct 3657 ms 229300 KB Output is correct
78 Correct 3426 ms 229264 KB Output is correct
79 Correct 3573 ms 229164 KB Output is correct
80 Correct 3646 ms 228312 KB Output is correct
81 Correct 3350 ms 216028 KB Output is correct
82 Correct 2840 ms 149732 KB Output is correct
83 Correct 3518 ms 229308 KB Output is correct
84 Correct 3520 ms 229036 KB Output is correct
85 Correct 3635 ms 229140 KB Output is correct
86 Correct 3461 ms 228100 KB Output is correct
87 Correct 3400 ms 216140 KB Output is correct
88 Correct 2806 ms 149796 KB Output is correct
89 Correct 2876 ms 172364 KB Output is correct
90 Correct 3308 ms 188064 KB Output is correct
91 Correct 3764 ms 206408 KB Output is correct
92 Correct 4006 ms 211364 KB Output is correct
93 Correct 3990 ms 218576 KB Output is correct
94 Correct 3722 ms 221208 KB Output is correct
95 Correct 3446 ms 226124 KB Output is correct
96 Correct 3436 ms 225316 KB Output is correct
97 Correct 3572 ms 225916 KB Output is correct
98 Correct 3453 ms 228352 KB Output is correct
99 Correct 3695 ms 225572 KB Output is correct
100 Correct 3285 ms 225764 KB Output is correct