oj.uz

Submission #579274

# Submission time Handle Problem Language Result Execution time Memory
579274 2022-06-18T17:25:13 Z temporary_juggernaut Dynamic Diameter (CEOI19_diameter) C++14
49 / 100
 5000 ms 196696 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;
	}
	//CALC ALLS
	if(!st[v].empty()){
		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);
	}
	//END
	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:185:3: note: in expansion of macro 'printl'
  185 |   printl("______________________");
      |   ^~~~~~
diameter.cpp:159:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |  scanf("%d%d%lld",&n,&q,&w[0]);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:163:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |   scanf("%d%d%lld",&edge[i].fr,&edge[i].sc,&w[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:172:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |   scanf("%lld%lld",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12884 KB Output is correct
2 Correct 7 ms 12884 KB Output is correct
3 Correct 9 ms 12884 KB Output is correct
4 Correct 7 ms 12884 KB Output is correct
5 Correct 7 ms 12812 KB Output is correct
6 Correct 7 ms 12884 KB Output is correct
7 Correct 8 ms 12884 KB Output is correct
8 Correct 8 ms 12884 KB Output is correct
9 Correct 8 ms 12884 KB Output is correct
10 Correct 9 ms 12976 KB Output is correct
11 Correct 8 ms 12884 KB Output is correct
12 Correct 7 ms 12884 KB Output is correct
13 Correct 7 ms 13012 KB Output is correct
14 Correct 7 ms 13012 KB Output is correct
15 Correct 8 ms 13052 KB Output is correct
16 Correct 7 ms 13012 KB Output is correct
17 Correct 8 ms 13052 KB Output is correct
18 Correct 10 ms 13056 KB Output is correct
19 Correct 37 ms 14676 KB Output is correct
20 Correct 38 ms 14620 KB Output is correct
21 Correct 47 ms 14660 KB Output is correct
22 Correct 45 ms 14652 KB Output is correct
23 Correct 65 ms 21828 KB Output is correct
24 Correct 83 ms 21688 KB Output is correct
25 Correct 103 ms 21840 KB Output is correct
26 Correct 100 ms 22124 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12884 KB Output is correct
2 Correct 7 ms 12884 KB Output is correct
3 Correct 8 ms 12852 KB Output is correct
4 Correct 22 ms 12884 KB Output is correct
5 Correct 90 ms 13212 KB Output is correct
6 Correct 8 ms 12852 KB Output is correct
7 Correct 8 ms 13736 KB Output is correct
8 Correct 8 ms 13688 KB Output is correct
9 Correct 12 ms 13784 KB Output is correct
10 Correct 36 ms 13740 KB Output is correct
11 Correct 109 ms 14180 KB Output is correct
12 Correct 15 ms 21460 KB Output is correct
13 Correct 16 ms 21460 KB Output is correct
14 Correct 19 ms 21460 KB Output is correct
15 Correct 53 ms 21564 KB Output is correct
16 Correct 200 ms 21964 KB Output is correct
17 Correct 184 ms 183848 KB Output is correct
18 Correct 193 ms 183768 KB Output is correct
19 Correct 212 ms 183848 KB Output is correct
20 Correct 251 ms 183972 KB Output is correct
21 Correct 531 ms 184456 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14548 KB Output is correct
2 Correct 51 ms 14664 KB Output is correct
3 Correct 236 ms 14816 KB Output is correct
4 Correct 422 ms 15244 KB Output is correct
5 Correct 71 ms 30508 KB Output is correct
6 Correct 152 ms 30692 KB Output is correct
7 Correct 449 ms 30840 KB Output is correct
8 Correct 847 ms 31116 KB Output is correct
9 Correct 352 ms 100428 KB Output is correct
10 Correct 461 ms 100604 KB Output is correct
11 Correct 996 ms 100776 KB Output is correct
12 Correct 1626 ms 101156 KB Output is correct
13 Correct 760 ms 187940 KB Output is correct
14 Correct 891 ms 188076 KB Output is correct
15 Correct 1595 ms 188196 KB Output is correct
16 Correct 2213 ms 188484 KB Output is correct
17 Correct 3670 ms 188684 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2919 ms 188932 KB Output is correct
2 Correct 3077 ms 188832 KB Output is correct
3 Correct 3013 ms 188888 KB Output is correct
4 Correct 3079 ms 188760 KB Output is correct
5 Correct 2966 ms 188484 KB Output is correct
6 Correct 2758 ms 187200 KB Output is correct
7 Correct 4258 ms 191360 KB Output is correct
8 Correct 4177 ms 191396 KB Output is correct
9 Correct 4094 ms 191364 KB Output is correct
10 Correct 4038 ms 191364 KB Output is correct
11 Correct 4116 ms 190916 KB Output is correct
12 Correct 4062 ms 189456 KB Output is correct
13 Execution timed out 5108 ms 196696 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12884 KB Output is correct
2 Correct 7 ms 12884 KB Output is correct
3 Correct 9 ms 12884 KB Output is correct
4 Correct 7 ms 12884 KB Output is correct
5 Correct 7 ms 12812 KB Output is correct
6 Correct 7 ms 12884 KB Output is correct
7 Correct 8 ms 12884 KB Output is correct
8 Correct 8 ms 12884 KB Output is correct
9 Correct 8 ms 12884 KB Output is correct
10 Correct 9 ms 12976 KB Output is correct
11 Correct 8 ms 12884 KB Output is correct
12 Correct 7 ms 12884 KB Output is correct
13 Correct 7 ms 13012 KB Output is correct
14 Correct 7 ms 13012 KB Output is correct
15 Correct 8 ms 13052 KB Output is correct
16 Correct 7 ms 13012 KB Output is correct
17 Correct 8 ms 13052 KB Output is correct
18 Correct 10 ms 13056 KB Output is correct
19 Correct 37 ms 14676 KB Output is correct
20 Correct 38 ms 14620 KB Output is correct
21 Correct 47 ms 14660 KB Output is correct
22 Correct 45 ms 14652 KB Output is correct
23 Correct 65 ms 21828 KB Output is correct
24 Correct 83 ms 21688 KB Output is correct
25 Correct 103 ms 21840 KB Output is correct
26 Correct 100 ms 22124 KB Output is correct
27 Correct 7 ms 12884 KB Output is correct
28 Correct 7 ms 12884 KB Output is correct
29 Correct 8 ms 12852 KB Output is correct
30 Correct 22 ms 12884 KB Output is correct
31 Correct 90 ms 13212 KB Output is correct
32 Correct 8 ms 12852 KB Output is correct
33 Correct 8 ms 13736 KB Output is correct
34 Correct 8 ms 13688 KB Output is correct
35 Correct 12 ms 13784 KB Output is correct
36 Correct 36 ms 13740 KB Output is correct
37 Correct 109 ms 14180 KB Output is correct
38 Correct 15 ms 21460 KB Output is correct
39 Correct 16 ms 21460 KB Output is correct
40 Correct 19 ms 21460 KB Output is correct
41 Correct 53 ms 21564 KB Output is correct
42 Correct 200 ms 21964 KB Output is correct
43 Correct 184 ms 183848 KB Output is correct
44 Correct 193 ms 183768 KB Output is correct
45 Correct 212 ms 183848 KB Output is correct
46 Correct 251 ms 183972 KB Output is correct
47 Correct 531 ms 184456 KB Output is correct
48 Correct 15 ms 14548 KB Output is correct
49 Correct 51 ms 14664 KB Output is correct
50 Correct 236 ms 14816 KB Output is correct
51 Correct 422 ms 15244 KB Output is correct
52 Correct 71 ms 30508 KB Output is correct
53 Correct 152 ms 30692 KB Output is correct
54 Correct 449 ms 30840 KB Output is correct
55 Correct 847 ms 31116 KB Output is correct
56 Correct 352 ms 100428 KB Output is correct
57 Correct 461 ms 100604 KB Output is correct
58 Correct 996 ms 100776 KB Output is correct
59 Correct 1626 ms 101156 KB Output is correct
60 Correct 760 ms 187940 KB Output is correct
61 Correct 891 ms 188076 KB Output is correct
62 Correct 1595 ms 188196 KB Output is correct
63 Correct 2213 ms 188484 KB Output is correct
64 Correct 3670 ms 188684 KB Output is correct
65 Correct 2919 ms 188932 KB Output is correct
66 Correct 3077 ms 188832 KB Output is correct
67 Correct 3013 ms 188888 KB Output is correct
68 Correct 3079 ms 188760 KB Output is correct
69 Correct 2966 ms 188484 KB Output is correct
70 Correct 2758 ms 187200 KB Output is correct
71 Correct 4258 ms 191360 KB Output is correct
72 Correct 4177 ms 191396 KB Output is correct
73 Correct 4094 ms 191364 KB Output is correct
74 Correct 4038 ms 191364 KB Output is correct
75 Correct 4116 ms 190916 KB Output is correct
76 Correct 4062 ms 189456 KB Output is correct
77 Execution timed out 5108 ms 196696 KB Time limit exceeded
78 Halted 0 ms 0 KB -