oj.uz

답안 #579270

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
579270 2022-06-18T17:01:57 Z temporary_juggernaut Dynamic Diameter (CEOI19_diameter) C++14
18 / 100
 5000 ms 180976 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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7380 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 4 ms 7380 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 4 ms 7508 KB Output is correct
16 Correct 5 ms 7508 KB Output is correct
17 Correct 5 ms 7508 KB Output is correct
18 Correct 5 ms 7508 KB Output is correct

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7380 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 4 ms 7380 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 4 ms 7508 KB Output is correct
16 Correct 5 ms 7508 KB Output is correct
17 Correct 5 ms 7508 KB Output is correct
18 Correct 5 ms 7508 KB Output is correct
19 Correct 37 ms 9076 KB Output is correct
20 Correct 35 ms 9044 KB Output is correct
21 Correct 41 ms 9192 KB Output is correct
22 Correct 45 ms 9116 KB Output is correct
23 Incorrect 63 ms 15896 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 18 ms 7508 KB Output is correct
5 Correct 80 ms 7912 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct
7 Correct 6 ms 8148 KB Output is correct
8 Correct 5 ms 8148 KB Output is correct
9 Correct 8 ms 8148 KB Output is correct
10 Correct 27 ms 8284 KB Output is correct
11 Correct 110 ms 8664 KB Output is correct
12 Correct 12 ms 15788 KB Output is correct
13 Correct 11 ms 15828 KB Output is correct
14 Correct 16 ms 15892 KB Output is correct
15 Correct 46 ms 15924 KB Output is correct
16 Correct 191 ms 16408 KB Output is correct
17 Correct 165 ms 173888 KB Output is correct
18 Correct 164 ms 173908 KB Output is correct
19 Correct 172 ms 173916 KB Output is correct
20 Correct 222 ms 173928 KB Output is correct
21 Correct 555 ms 174608 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 9044 KB Output is correct
2 Correct 54 ms 9096 KB Output is correct
3 Correct 235 ms 9208 KB Output is correct
4 Correct 500 ms 9592 KB Output is correct
5 Correct 58 ms 24136 KB Output is correct
6 Incorrect 191 ms 24228 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3158 ms 175468 KB Output is correct
2 Correct 3453 ms 175396 KB Output is correct
3 Correct 3442 ms 175240 KB Output is correct
4 Correct 3393 ms 175184 KB Output is correct
5 Correct 3425 ms 175188 KB Output is correct
6 Correct 3207 ms 175364 KB Output is correct
7 Correct 4468 ms 177416 KB Output is correct
8 Correct 4503 ms 177352 KB Output is correct
9 Correct 4553 ms 177436 KB Output is correct
10 Correct 4488 ms 177420 KB Output is correct
11 Correct 4624 ms 177348 KB Output is correct
12 Correct 4277 ms 177444 KB Output is correct
13 Correct 4908 ms 180864 KB Output is correct
14 Correct 4856 ms 180976 KB Output is correct
15 Execution timed out 5027 ms 180784 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7380 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 4 ms 7380 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 4 ms 7508 KB Output is correct
16 Correct 5 ms 7508 KB Output is correct
17 Correct 5 ms 7508 KB Output is correct
18 Correct 5 ms 7508 KB Output is correct
19 Correct 37 ms 9076 KB Output is correct
20 Correct 35 ms 9044 KB Output is correct
21 Correct 41 ms 9192 KB Output is correct
22 Correct 45 ms 9116 KB Output is correct
23 Incorrect 63 ms 15896 KB Output isn't correct
24 Halted 0 ms 0 KB -