Submission #836386

#	Time	Username	Problem	Language	Result	Execution time	Memory
836386		sunwukong123	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	541 ms	137616 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;
#define int long long 
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 400005;
const int inf=1000000500ll;
const int oo =1000000000000000000ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
int n;
vector<pi> adj[MAXN];
/*
this is essentially finding diameter while updating some edges from weight 1 to weight 0
when should you update an edge from weight 1 to weight 0?
at t=min(sz[a],sz[b])
so just use the dynamicdiameter code to solve this as well
note that you can probably simplify many things, because we are always removing the leaf, and the edges are unweighted.
*/
int sz[MAXN];
vector<int> T[MAXN];
int id[MAXN];
int TIME;
int in[MAXN];
int out[MAXN];
struct node {
	int s,e,m;
	int a,b,c,ab,bc,abc;
	int lazy;
	node *l, *r;
	node(int _s, int _e){
		s=_s;e=_e;m=(s+e)/2;
		a=b=c=ab=bc=abc=lazy=0;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	void value(){
		if(lazy==0)return;
		a+=lazy;
		b-=2*lazy;
		c+=lazy;
		ab-=lazy;
		bc-=lazy;
		if(s!=e){
			l->lazy+=lazy;
			r->lazy+=lazy;
		}
		lazy=0;
	}
	void update(int x, int y, int nval){
		value();
		if(s==x&&e==y){
			lazy+=nval;
			return;
		}
		if(x>m)r->update(x,y,nval);
		else if(y<=m)l->update(x,y,nval);
		else {
			l->update(x,m,nval);
			r->update(m+1,y,nval);
		}

		l->value();r->value();
		a=max(l->a,r->a);
		b=max(l->b,r->b);
		c=max(l->c,r->c);
		ab=max({l->ab,r->ab,l->a+r->b});
		bc=max({l->bc,r->bc,l->b+r->c});
		abc=max({l->abc,r->abc,l->a+r->bc,l->ab+r->c});
		
	}
}*seg=new node(0,MAXN);
void dfs(int x, int p){
	in[x]=TIME++;
	sz[x]=1;
	for(auto v:adj[x])if(v.first!=p){
		dfs(v.first,x);
		sz[x]+=sz[v.first];
		id[v.second]=v.first;
		out[x]=TIME++;
	}
	if(out[x]==0)out[x]=in[x];

	int ti=min(sz[x],n-sz[x]);
	T[ti].push_back(x);
}
int32_t main() 
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i=1;i<=n-1;i++){
		int a,b; cin >> a >> b;
		adj[a].push_back({b,i});
		adj[b].push_back({a,i});
	}

	dfs(1,-1);


	for(int i=1;i<=n-1;i++){
		seg->update(in[id[i]],out[id[i]],1);
	}

	for(int i=1;i<=n/2;i++){
		cout<<"1\n";
		cout<<1+seg->abc<<'\n';
		for(auto x:T[i]){

			seg->update(in[x],out[x],-1);
		}
	}
	if(n%2==1)cout<<"1\n";
}

• Subtask 1: 4 / 4
• Subtask 2: 16 / 16
• Subtask 3: 80 / 80