oj.uz

Submission #579269

# Submission time Handle Problem Language Result Execution time Memory
579269 2022-06-18T17:00:32 Z temporary_juggernaut Dynamic Diameter (CEOI19_diameter) C++14
18 / 100
 5000 ms 180916 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;
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);
	}
	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(tree[depth[v]].get(tin[child][depth[v]],tout[child][depth[v]],1,1,n)));
	tree[depth[v]].update(tin[x][depth[v]],tout[x][depth[v]],val,1,1,n);
	st[v].insert(tree[depth[v]].get(tin[child][depth[v]],tout[child][depth[v]],1,1,n));
	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:170:3: note: in expansion of macro 'printl'
  170 |   printl("______________________");
      |   ^~~~~~
diameter.cpp:144:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |  scanf("%d%d%lld",&n,&q,&w[0]);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:148:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |   scanf("%d%d%lld",&edge[i].fr,&edge[i].sc,&w[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:157:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |   scanf("%lld%lld",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 6 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 6 ms 7380 KB Output is correct
5 Correct 5 ms 7412 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 5 ms 7508 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 4 ms 7380 KB Output is correct
13 Correct 4 ms 7508 KB Output is correct
14 Correct 4 ms 7508 KB Output is correct
15 Correct 7 ms 7484 KB Output is correct
16 Correct 5 ms 7508 KB Output is correct
17 Correct 5 ms 7508 KB Output is correct
18 Correct 6 ms 7508 KB Output is correct
19 Correct 30 ms 9044 KB Output is correct
20 Correct 36 ms 9200 KB Output is correct
21 Correct 42 ms 9076 KB Output is correct
22 Correct 50 ms 9224 KB Output is correct
23 Incorrect 72 ms 15956 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 4 ms 7436 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 23 ms 7500 KB Output is correct
5 Correct 76 ms 7768 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 5 ms 8148 KB Output is correct
8 Correct 5 ms 8176 KB Output is correct
9 Correct 9 ms 8272 KB Output is correct
10 Correct 28 ms 8276 KB Output is correct
11 Correct 114 ms 8612 KB Output is correct
12 Correct 12 ms 15772 KB Output is correct
13 Correct 11 ms 15884 KB Output is correct
14 Correct 15 ms 15908 KB Output is correct
15 Correct 42 ms 15952 KB Output is correct
16 Correct 169 ms 16256 KB Output is correct
17 Correct 173 ms 173880 KB Output is correct
18 Correct 167 ms 173880 KB Output is correct
19 Correct 177 ms 173956 KB Output is correct
20 Correct 250 ms 173944 KB Output is correct
21 Correct 491 ms 174604 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9044 KB Output is correct
2 Correct 58 ms 9088 KB Output is correct
3 Correct 247 ms 9312 KB Output is correct
4 Correct 503 ms 9620 KB Output is correct
5 Correct 63 ms 24140 KB Output is correct
6 Incorrect 231 ms 24376 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3492 ms 175160 KB Output is correct
2 Correct 3599 ms 175184 KB Output is correct
3 Correct 3367 ms 175284 KB Output is correct
4 Correct 3398 ms 175228 KB Output is correct
5 Correct 3313 ms 175220 KB Output is correct
6 Correct 3187 ms 175328 KB Output is correct
7 Correct 4787 ms 177448 KB Output is correct
8 Correct 4484 ms 177432 KB Output is correct
9 Correct 4657 ms 177512 KB Output is correct
10 Correct 4613 ms 177420 KB Output is correct
11 Correct 4515 ms 177296 KB Output is correct
12 Correct 4312 ms 177404 KB Output is correct
13 Execution timed out 5009 ms 180916 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 6 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 6 ms 7380 KB Output is correct
5 Correct 5 ms 7412 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 5 ms 7508 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 4 ms 7380 KB Output is correct
13 Correct 4 ms 7508 KB Output is correct
14 Correct 4 ms 7508 KB Output is correct
15 Correct 7 ms 7484 KB Output is correct
16 Correct 5 ms 7508 KB Output is correct
17 Correct 5 ms 7508 KB Output is correct
18 Correct 6 ms 7508 KB Output is correct
19 Correct 30 ms 9044 KB Output is correct
20 Correct 36 ms 9200 KB Output is correct
21 Correct 42 ms 9076 KB Output is correct
22 Correct 50 ms 9224 KB Output is correct
23 Incorrect 72 ms 15956 KB Output isn't correct
24 Halted 0 ms 0 KB -