oj.uz

Submission #579271

# Submission time Handle Problem Language Result Execution time Memory
579271 2022-06-18T17:10:15 Z temporary_juggernaut Dynamic Diameter (CEOI19_diameter) C++14
42 / 100
 4508 ms 197100 KB 
#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
    #define printl(args...) printf(args)
#else
    #define printl(args...) 0
#endif
int n,q;
int timer[20];
int tin[100005][20];
int tout[100005][20];
ll w[100005];
multiset<ll>st[100005];
pair<int,int>edge[100005];
vector<pair<int,int>>g[100005];
bool vis[100005];
int sz[100005];
int par[100005];
int depth[100005];
int prepar[100005][20];
struct MultiSegmentTree{
	vector<ll>tree;
	vector<ll>lazy;
	MultiSegmentTree(){
	}
	MultiSegmentTree(int n){
		tree.assign(n<<2|3,0ll);
		lazy.assign(n<<2|3,0ll);
	}
	void push(int v,bool bit){
		if(bit){
			lazy[v<<1]+=lazy[v];
			lazy[v<<1|1]+=lazy[v];
		}
		tree[v]+=lazy[v];
		lazy[v]=0;
	}
	ll get(int ql,int qr,int v,int l,int r){
		if(qr<l||r<ql)return 0ll;
		push(v,l^r);
		if(ql<=l&&r<=qr)return tree[v];
		int mid=(l+r)>>1;
		return max(get(ql,qr,v<<1,l,mid),get(ql,qr,v<<1|1,mid+1,r));
	}
	void update(int ql,int qr,ll val,int v,int l,int r){
		push(v,l^r);
		if(qr<l||r<ql)return;
		if(ql<=l&&r<=qr){
			lazy[v]+=val;
			push(v,l^r);
			return;
		}
		int mid=(l+r)>>1;
		update(ql,qr,val,v<<1,l,mid);
		update(ql,qr,val,v<<1|1,mid+1,r);
		tree[v]=max(tree[v<<1],tree[v<<1|1]);
	}
};
MultiSegmentTree tree[20],alls;
void build_sz(int v,int p){
	sz[v]=1;
	for(auto &to:g[v])if((to.fr^p)&&(!vis[to.fr])){
		build_sz(to.fr,v);
		sz[v]+=sz[to.fr];
	}
}
int centroid(int v,int p,int sz){
	bool can;
	while(true){
		can=true;
		for(auto &to:g[v])if((to.fr^p)&&(!vis[to.fr])){
			if(::sz[to.fr]>sz){
				can=false;
				p=v;
				v=to.fr;
				break;
			}
		}
		if(can)return v;
	}
}
void build_tin(int v,int p,int &depth,int &kylych){
	tin[v][depth]=++timer[depth];
	prepar[v][depth]=kylych;
	for(auto &to:g[v])if((to.fr^p)&&(!vis[to.fr]))build_tin(to.fr,v,depth,kylych);
	tout[v][depth]=timer[depth];
}
ll cash;
unordered_map<int,ll>csh[100005];
void go(int v,int p,int &depth,ll kylych){
	tree[depth].update(tin[v][depth],tin[v][depth],kylych,1,1,n);
	umax(cash,kylych);
	for(auto &to:g[v])if((to.fr^p)&&(!vis[to.fr]))go(to.fr,v,depth,kylych+w[to.sc]);
}
void build(int v,int p,int dep){
	build_sz(v,0);
	v=centroid(v,0,sz[v]>>1);
	tin[v][dep]=++timer[dep];
	for(auto &to:g[v])if((to.fr^p)&&(!vis[to.fr])){
		build_tin(to.fr,v,dep,to.fr);
	}
	tout[v][dep]=timer[dep];
	for(auto &to:g[v])if((to.fr^p)&&(!vis[to.fr])){
		cash=0;
		go(to.fr,v,dep,w[to.sc]);
		st[v].insert(cash);
		csh[v][to.fr]=cash;
	}
	par[v]=p;
	depth[v]=dep;
	vis[v]=true;
	for(auto &to:g[v])if(!vis[to.fr])build(to.fr,v,dep+1);
}
ll ans;
int cand_x,cand_y;
void edit(int v,ll val){
	int x=cand_x;
	int y=cand_y;
	if(tin[x][depth[v]]<tin[y][depth[v]])swap(x,y);
	int child=prepar[x][depth[v]];
	st[v].erase(st[v].find(csh[v][child]));
	tree[depth[v]].update(tin[x][depth[v]],tout[x][depth[v]],val,1,1,n);
	csh[v][child]=tree[depth[v]].get(tin[child][depth[v]],tout[child][depth[v]],1,1,n);
	st[v].insert(csh[v][child]);
	ll ans=0;
	auto it=st[v].rbegin();
	ans+=*it;
	if((int)st[v].size()!=1){
		it++;
		ans+=*it;
	}
	alls.update(v,v,ans-alls.get(v,v,1,1,n),1,1,n);
}
int main(){
	scanf("%d%d%lld",&n,&q,&w[0]);
	for(int i=0;i<20;i++)tree[i]=MultiSegmentTree(n);
	alls=MultiSegmentTree(n);
	for(int i=1;i^n;i++){
		scanf("%d%d%lld",&edge[i].fr,&edge[i].sc,&w[i]);
		g[edge[i].fr].emplace_back(edge[i].sc,i);
		g[edge[i].sc].emplace_back(edge[i].fr,i);
	}
	build(1,0,0);
	for(int i=1;i^n;i++)if(depth[edge[i].fr]>depth[edge[i].sc])swap(edge[i].fr,edge[i].sc);
	while(q--){
		ll x;
		ll y;
		scanf("%lld%lld",&x,&y);
		x=((x+ans)%(n-1))+1;
		y=(y+ans)%w[0];
		ll pivot=y-w[x];
		w[x]=y;
		cand_x=edge[x].fr;
		cand_y=edge[x].sc;
		x=edge[x].fr;
		while(x){
			edit(x,pivot);
			x=par[x];
		}
		ans=alls.get(1,n,1,1,n);
		printl("______________________");
		printf("%lld\n",ans);
	}
}

Compilation message

diameter.cpp: In function 'int main()':
diameter.cpp:18:29: warning: statement has no effect [-Wunused-value]
   18 |     #define printl(args...) 0
      |                             ^
diameter.cpp:173:3: note: in expansion of macro 'printl'
  173 |   printl("______________________");
      |   ^~~~~~
diameter.cpp:147:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |  scanf("%d%d%lld",&n,&q,&w[0]);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:151:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |   scanf("%d%d%lld",&edge[i].fr,&edge[i].sc,&w[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:160:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |   scanf("%lld%lld",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12884 KB Output is correct
2 Correct 8 ms 12884 KB Output is correct
3 Correct 7 ms 12884 KB Output is correct
4 Correct 7 ms 12900 KB Output is correct
5 Correct 7 ms 12856 KB Output is correct
6 Correct 7 ms 12828 KB Output is correct
7 Correct 9 ms 12884 KB Output is correct
8 Correct 7 ms 12884 KB Output is correct
9 Correct 7 ms 12884 KB Output is correct
10 Correct 7 ms 12884 KB Output is correct
11 Correct 7 ms 12884 KB Output is correct
12 Correct 8 ms 12884 KB Output is correct
13 Correct 10 ms 12968 KB Output is correct
14 Correct 8 ms 13012 KB Output is correct
15 Correct 8 ms 13012 KB Output is correct
16 Correct 8 ms 13012 KB Output is correct
17 Correct 10 ms 13012 KB Output is correct
18 Correct 9 ms 13012 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12884 KB Output is correct
2 Correct 8 ms 12884 KB Output is correct
3 Correct 7 ms 12884 KB Output is correct
4 Correct 7 ms 12900 KB Output is correct
5 Correct 7 ms 12856 KB Output is correct
6 Correct 7 ms 12828 KB Output is correct
7 Correct 9 ms 12884 KB Output is correct
8 Correct 7 ms 12884 KB Output is correct
9 Correct 7 ms 12884 KB Output is correct
10 Correct 7 ms 12884 KB Output is correct
11 Correct 7 ms 12884 KB Output is correct
12 Correct 8 ms 12884 KB Output is correct
13 Correct 10 ms 12968 KB Output is correct
14 Correct 8 ms 13012 KB Output is correct
15 Correct 8 ms 13012 KB Output is correct
16 Correct 8 ms 13012 KB Output is correct
17 Correct 10 ms 13012 KB Output is correct
18 Correct 9 ms 13012 KB Output is correct
19 Correct 30 ms 14624 KB Output is correct
20 Correct 34 ms 14592 KB Output is correct
21 Correct 41 ms 14620 KB Output is correct
22 Correct 44 ms 14676 KB Output is correct
23 Incorrect 62 ms 21864 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12884 KB Output is correct
2 Correct 10 ms 12880 KB Output is correct
3 Correct 9 ms 12884 KB Output is correct
4 Correct 21 ms 12972 KB Output is correct
5 Correct 72 ms 13280 KB Output is correct
6 Correct 7 ms 12884 KB Output is correct
7 Correct 8 ms 13656 KB Output is correct
8 Correct 8 ms 13652 KB Output is correct
9 Correct 10 ms 13652 KB Output is correct
10 Correct 27 ms 13828 KB Output is correct
11 Correct 115 ms 14188 KB Output is correct
12 Correct 18 ms 21588 KB Output is correct
13 Correct 18 ms 21460 KB Output is correct
14 Correct 18 ms 21460 KB Output is correct
15 Correct 42 ms 21584 KB Output is correct
16 Correct 160 ms 22008 KB Output is correct
17 Correct 204 ms 183888 KB Output is correct
18 Correct 187 ms 183876 KB Output is correct
19 Correct 191 ms 183844 KB Output is correct
20 Correct 252 ms 183904 KB Output is correct
21 Correct 522 ms 184456 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14548 KB Output is correct
2 Correct 57 ms 14732 KB Output is correct
3 Correct 267 ms 14856 KB Output is correct
4 Correct 429 ms 15116 KB Output is correct
5 Correct 67 ms 30480 KB Output is correct
6 Incorrect 210 ms 30536 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3279 ms 188760 KB Output is correct
2 Correct 3158 ms 188752 KB Output is correct
3 Correct 3204 ms 188796 KB Output is correct
4 Correct 3084 ms 188724 KB Output is correct
5 Correct 3039 ms 188368 KB Output is correct
6 Correct 2823 ms 187100 KB Output is correct
7 Correct 4115 ms 191304 KB Output is correct
8 Correct 4165 ms 191264 KB Output is correct
9 Correct 3975 ms 191464 KB Output is correct
10 Correct 4040 ms 191432 KB Output is correct
11 Correct 4014 ms 190928 KB Output is correct
12 Correct 3666 ms 189736 KB Output is correct
13 Correct 4369 ms 196696 KB Output is correct
14 Correct 4412 ms 196804 KB Output is correct
15 Correct 4394 ms 196632 KB Output is correct
16 Correct 4429 ms 196532 KB Output is correct
17 Correct 4237 ms 195468 KB Output is correct
18 Correct 3900 ms 191952 KB Output is correct
19 Correct 4379 ms 197100 KB Output is correct
20 Correct 4508 ms 196752 KB Output is correct
21 Correct 4444 ms 196668 KB Output is correct
22 Correct 4416 ms 196708 KB Output is correct
23 Correct 4303 ms 195572 KB Output is correct
24 Correct 3895 ms 192016 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12884 KB Output is correct
2 Correct 8 ms 12884 KB Output is correct
3 Correct 7 ms 12884 KB Output is correct
4 Correct 7 ms 12900 KB Output is correct
5 Correct 7 ms 12856 KB Output is correct
6 Correct 7 ms 12828 KB Output is correct
7 Correct 9 ms 12884 KB Output is correct
8 Correct 7 ms 12884 KB Output is correct
9 Correct 7 ms 12884 KB Output is correct
10 Correct 7 ms 12884 KB Output is correct
11 Correct 7 ms 12884 KB Output is correct
12 Correct 8 ms 12884 KB Output is correct
13 Correct 10 ms 12968 KB Output is correct
14 Correct 8 ms 13012 KB Output is correct
15 Correct 8 ms 13012 KB Output is correct
16 Correct 8 ms 13012 KB Output is correct
17 Correct 10 ms 13012 KB Output is correct
18 Correct 9 ms 13012 KB Output is correct
19 Correct 30 ms 14624 KB Output is correct
20 Correct 34 ms 14592 KB Output is correct
21 Correct 41 ms 14620 KB Output is correct
22 Correct 44 ms 14676 KB Output is correct
23 Incorrect 62 ms 21864 KB Output isn't correct
24 Halted 0 ms 0 KB -