oj.uz

답안 #579268

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
579268 2022-06-18T16:57:04 Z temporary_juggernaut Dynamic Diameter (CEOI19_diameter) C++14
42 / 100
 4953 ms 182728 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 7424 KB Output is correct
6 Correct 4 ms 7368 KB Output is correct
7 Correct 6 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 5 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 7492 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 7424 KB Output is correct
6 Correct 4 ms 7368 KB Output is correct
7 Correct 6 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 5 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 7492 KB Output is correct
18 Correct 5 ms 7508 KB Output is correct
19 Correct 31 ms 9044 KB Output is correct
20 Correct 36 ms 9124 KB Output is correct
21 Correct 42 ms 9136 KB Output is correct
22 Correct 49 ms 9164 KB Output is correct
23 Incorrect 59 ms 15956 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 4 ms 7380 KB Output is correct
3 Correct 7 ms 7372 KB Output is correct
4 Correct 19 ms 7600 KB Output is correct
5 Correct 76 ms 8560 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 5 ms 8144 KB Output is correct
8 Correct 5 ms 8148 KB Output is correct
9 Correct 8 ms 8148 KB Output is correct
10 Correct 28 ms 8464 KB Output is correct
11 Correct 112 ms 9544 KB Output is correct
12 Correct 13 ms 15828 KB Output is correct
13 Correct 11 ms 15828 KB Output is correct
14 Correct 14 ms 15944 KB Output is correct
15 Correct 45 ms 16224 KB Output is correct
16 Correct 159 ms 17288 KB Output is correct
17 Correct 170 ms 175104 KB Output is correct
18 Correct 169 ms 175024 KB Output is correct
19 Correct 177 ms 175152 KB Output is correct
20 Correct 215 ms 175404 KB Output is correct
21 Correct 544 ms 176188 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 9044 KB Output is correct
2 Correct 55 ms 9200 KB Output is correct
3 Correct 272 ms 9732 KB Output is correct
4 Correct 481 ms 10448 KB Output is correct
5 Correct 64 ms 24228 KB Output is correct
6 Incorrect 195 ms 24428 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3142 ms 175224 KB Output is correct
2 Correct 3424 ms 177660 KB Output is correct
3 Correct 3323 ms 177656 KB Output is correct
4 Correct 3298 ms 177692 KB Output is correct
5 Correct 3348 ms 177560 KB Output is correct
6 Correct 2973 ms 177924 KB Output is correct
7 Correct 4429 ms 179840 KB Output is correct
8 Correct 4578 ms 179300 KB Output is correct
9 Correct 4536 ms 179164 KB Output is correct
10 Correct 4415 ms 179220 KB Output is correct
11 Correct 4521 ms 179316 KB Output is correct
12 Correct 4177 ms 179244 KB Output is correct
13 Correct 4934 ms 182508 KB Output is correct
14 Correct 4795 ms 182608 KB Output is correct
15 Correct 4811 ms 182644 KB Output is correct
16 Correct 4809 ms 182644 KB Output is correct
17 Correct 4617 ms 182004 KB Output is correct
18 Correct 4234 ms 180612 KB Output is correct
19 Correct 4870 ms 182540 KB Output is correct
20 Correct 4792 ms 182728 KB Output is correct
21 Correct 4953 ms 182548 KB Output is correct
22 Correct 4827 ms 182500 KB Output is correct
23 Correct 4676 ms 181940 KB Output is correct
24 Correct 4226 ms 180572 KB Output is correct

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 7424 KB Output is correct
6 Correct 4 ms 7368 KB Output is correct
7 Correct 6 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 5 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 7492 KB Output is correct
18 Correct 5 ms 7508 KB Output is correct
19 Correct 31 ms 9044 KB Output is correct
20 Correct 36 ms 9124 KB Output is correct
21 Correct 42 ms 9136 KB Output is correct
22 Correct 49 ms 9164 KB Output is correct
23 Incorrect 59 ms 15956 KB Output isn't correct
24 Halted 0 ms 0 KB -