Submission #802740

#	Time	Username	Problem	Language	Result	Execution time	Memory
802740		MohamedAliSaidane	Meetings 2 (JOI21_meetings2)	C++14	0 / 100	6 ms	9740 KiB

meetings2

    #include<bits/stdc++.h>
    using namespace std;
     
    typedef pair<int,int> pii;
    typedef vector<int> vi;
     
    #define ff first
    #define ss second
    #define pb push_back
    #define all(x) (x).begin(),(x).end()
    const int nax = 2e5 + 5;
     
    int n;
    vi adj[nax];
    int sz[20][nax], mark[nax], dis[20][nax], ans[nax];
    struct node
    {
    	int maxi = 0;
    	int maxi2 = 0;
    	int sum = 0;
    	int lazy1 = 0, lazy2 = 0;
    };
    node bss;
    vector<node> st;
    vi nodes[nax];
     
    void mx(int p, int val)
    {
    	if(st[p].maxi <= val)
    	{
    		st[p].maxi2 = st[p].maxi;
    		st[p].maxi = val;
    	}
    	else if(st[p].maxi2 < val)
    	{
    		st[p].maxi2 = val;
    	}
    	st[p].sum = max(st[p].sum, st[p].maxi + st[p].maxi2);
     
    }
    void mxlz(int p, int val)
    {
    	if(st[p].lazy1 <= val)
    	{
    		st[p].lazy2 = st[p].lazy1;
    		st[p].lazy1 = val;
    	}
    	else if(st[p].lazy2 < val)
    	{
    		st[p].lazy2 = val;
    	}
     
    }
    void propagate(int p, int l, int r)
    {
    	if(st[p].lazy1 != 0)
    	{
    		if(l != r)
    		{
    			mxlz(2 * p, st[p].lazy1);
    			mxlz(2 * p, st[p].lazy2);
    			mxlz(2 * p + 1, st[p].lazy1);
    			mxlz(2 * p + 1, st[p].lazy2);
    		}		
    		mx(p, st[p].lazy1);
    		mx(p, st[p].lazy2);
    		st[p].lazy1 = st[p].lazy2 = 0;
    	}
    }
    int query(int p, int l, int r, int i, int j)
    {
    	propagate(p, l, r);
    	if(i > j)
    		return 0;
    	if(l >= i && r <= j)
    		return st[p].sum;
    	int m = (l + r)/2;
    	return max(query(2 * p, l, m, i, min(j, m)),
    				query(2 * p + 1, m + 1, r, max(i, m + 1), j));
    }
    void update(int p, int l, int r, int i, int j, int val)
    {
    	propagate(p, l, r);
    	if(i > j)
    		return ;
    	if(l >= i && r <= j)
    	{
    		mxlz(p, val);
    		propagate(p, l, r);
    		return ;
    	}
    	int m = (l + r)/2;
    	update(2 * p, l, m, i, min(j, m), val);
    	update(2 * p + 1, m + 1, r, max(i, m + 1), j, val);
    	st[p].sum = max(st[2 * p].sum, st[2 * p + 1].sum);
    }
    int getsz(int x, int d, int cur, int p = -1)
    {
    	sz[d][x] = 1;
    	dis[d][x] = cur ;
    	for(auto e: adj[x])
    	{
    		if(mark[e] || (e == p))
    			continue;
    		sz[d][x] += getsz(e, d, cur + 1, x);
    	}
    	return sz[d][x];
    }
    int get_centroid(int x, int d, int s, int p = -1)
    {
    	for(auto e: adj[x])
    	{
    		if(mark[e] || (e == p))
    			continue;
    		if(sz[d][e] > s/2)
    			return get_centroid(e, d, s, x);
    	}
    	return x;
    }
    int centroid(int x, int d = 0)
    {
    	x = get_centroid(x, d, getsz(x, d, 0));
    	getsz(x, d, 0);
    	nodes[x].pb(x);
    	mark[x] = 1;
    	vi C;
    	for(auto e: adj[x])
    	{
    		if(mark[e])
    			continue;
    		int c = centroid(e, d + 1);
    		C.pb(c);
    	}
    	int k = 1;
    	while(k < sz[d][x] + 1)
    		k = (k << 1);
    	st.assign(2 * k + 1, bss);
    	for(auto c: C)
    	{
    		vector<pii> v;
    		for(auto e: nodes[c])
    		{
    			nodes[x].pb(e);
    			v.pb({dis[d][e], sz[d][e]});
    			//cout << '\t' << x << ' ' << e << ' ' <<  dis[d][e] << ' ' << sz[d][e] << '\n';
    		}
    		nodes[c].clear();
    		sort(all(v));
    		reverse(all(v));
    		int prev = 0;
    		for(auto e: v)
    		{
    			if(e.ss <= prev)
    				continue;
    			update(1, 0, k - 1, prev + 1, e.ss, e.ff );
    			//if(x == 3 && e.ss >= 3)
    			///	cout << "\t\t" << e.ff << '\n';
    			prev = e.ss;
    			//cout << '\t'<<  x << ' ' << e.ff << ' ' << e.ss << '\n';
    		}
    	}
    	
    	for(int i = 1; i <= sz[d][x]; i++)
    	{
    		ans[i] = max(ans[i], query(1, 0, k - 1, i, sz[d][x]));
    		//if(x == 2)
    			//cout <<  query(1, 0, k - 1, i, sz[d][x]) << " ";
    	}
    	//cout << '\n';
    	//cout << x << endl;
    	
    	return x;
     
    }
    void solve()
    {
    	cin >> n;
    	for(int i = 1; i < n; i ++)
    	{
    		int a, b;
    		cin >> a >> b;
    		adj[a].pb(b);
    		adj[b].pb(a);
    	}
    	centroid(1);
    	for(int i = 1; i <= n; i++)
    	{
    		if(i & 1)
    			cout << 1 << '\n';
    		else
    			cout << ans[i/2]+ 1 << '\n';
    	}
    }
    int32_t main()
    {
    	ios::sync_with_stdio(false);
    	cin.tie(0); cout.tie(0);
    	/*
    	#ifndef ONLINE_JUDGE
    	freopen("input.txt", "r", stdin);
    	freopen("output.txt", "w", stdout);
    	#endif
    	*/
    	int tt = 1;
    	while(tt--)
    		solve();
     
    }
    /*
    5
    1 2
    2 3
    4 2
    3 5
    */

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