oj.uz

Submission #408436

# Submission time Handle Problem Language Result Execution time Memory
408436 2021-05-19T07:26:45 Z ryansee Meetings 2 (JOI21_meetings2) C++14
0 / 100
 6 ms 4992 KB 
#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusive
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

using ll=long long;
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>; 

long long LLINF = 1e18;
int INF = 1e9+1e6;
#define MAXN (200006)
int n, p[MAXN][18], dist[MAXN], st[MAXN], en[MAXN], co, sz[MAXN];
vector<int> v[MAXN];
void dfs(int x,int par) {
	st[x] = co++, p[x][0]=par, sz[x] = 1;
	for(auto i:v[x]) if(i^par) dist[i]=dist[x]+1, dfs(i, x), sz[x] += sz[i];
	en[x] = co-1;
}
bool isp(int a,int b) { return st[a]<=st[b]&&en[a]>=en[b]; }
int lca(int x,int y) {
	if(isp(x,y)) return x;
	if(isp(y,x)) return y;
	DEC(i,17,0) if(!isp(p[x][i], y)) x=p[x][i];
	return p[x][0];
}
int disty(int a,int b) { return dist[a]+dist[b]-2*dist[lca(a,b)]; }
int A, B, out[MAXN];
int main() {
	FAST
	cin>>n;
	FOR(i,1,n-1) {
		int a, b;
		cin>>a>>b;
		v[a].eb(b), v[b].eb(a);
	}
	dfs(1, 1);
	FOR(i,1,n) {
		int mx = n - sz[i];
		for(auto j:v[i]) if(j^p[i][0]) mx = max(mx, sz[j]);
		sz[i] = n-mx;
	}
	FOR(i,1,n) sz[i] = min(sz[i], n - sz[i] + 1);
	FOR(j,1,17) FOR(i,1,n) p[i][j]=p[p[i][j-1]][j-1];
	A=B=-1;
	vector<pi> V;
	FOR(i,1,n) {
		// cerr<<i<<": "<<sz[i]<<'\n';
		 V.eb(sz[i], i);
	 }
	sort(all(V));
	for(ll i=n/2;i>=1;--i) {
		while(V.size() && V.back().f >= i) {
			int x = V.back().s; V.pop_back();
			if(A==-1) A=B=x;
			else {
				if(disty(x, A) >= disty(A, B) && disty(x, A) >= disty(x, B)) {
					B = x;
				} else if(disty(x, B) >= disty(A, B)) {
					A = x;
				}
			}
		}
		if(A == -1) out[i*2]=0;
		else out[i*2] = disty(A, B);
	}
	FOR(i,1,n) cout<<out[i]+1<<'\n';
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 5 ms 4992 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 4 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 6 ms 4992 KB Output is correct
10 Correct 4 ms 4940 KB Output is correct
11 Correct 5 ms 4940 KB Output is correct
12 Incorrect 4 ms 4960 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 5 ms 4992 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 4 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 6 ms 4992 KB Output is correct
10 Correct 4 ms 4940 KB Output is correct
11 Correct 5 ms 4940 KB Output is correct
12 Incorrect 4 ms 4960 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 5 ms 4992 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 4 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 6 ms 4992 KB Output is correct
10 Correct 4 ms 4940 KB Output is correct
11 Correct 5 ms 4940 KB Output is correct
12 Incorrect 4 ms 4960 KB Output isn't correct
13 Halted 0 ms 0 KB -