Submission #549990

#	Time	Username	Problem	Language	Result	Execution time	Memory
549990		hohohaha	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	251 ms	94284 KiB

meetings2

#include<bits/stdc++.h>
using namespace std;

#define fori(i, l, r) for(int i = (int) (l); i <= (int) (r); i++) 
#define ford(i, r, l) for(int i = (int) (r); i >= (int) (l); i--) 
#define ii pair<int, int> 
#define fi first
#define se second
#define vi vector<int> 
#define eb emplace_back
#define em emplace
#define sp ' ' 
#define endl '\n'
#define int long long
const int maxn =2e5 +5; 
int n; 
vi g[maxn]; 
int tim; 
int tin[maxn]; 
int dep[maxn]; 
int sz[maxn]; 
int euler[maxn * 2]; 
int lca[21][maxn * 2]; 
vector<int> nodes_sz[maxn]; 
pair<int, ii> Dia; 
int ans[maxn]; 

void dfs_sz(int u, int p) { 
	sz[u] = 1; 
	for(int v: g[u]) { 
		if(v - p) { 
			dfs_sz(v, u); 
			sz[u] += sz[v]; 
		}
	}
}
int get_cen(int u, int p) { 
	for(int v: g[u]) { 
		if(v - p and sz[v] * 2 > sz[1]) return get_cen(v, u); 
	}
	return u; 
}
void dfs_prep(int u, int p) { 
	sz[u] = 1; 
	++tim; 
	tin[u] = tim;
	euler[tim] = u; 
	
	for(int v: g[u]) { 
		if(v - p) {
			dep[v] = dep[u] + 1; 
			dfs_prep(v, u); 
			sz[u] += sz[v]; 
			++tim; 
			euler[tim] = u; 
		}
	}
}

int hg(int u, int v) { 
	return dep[u] < dep[v]? u: v; 
}
int get_lca(int u, int v) { 
	int l = tin[u], r = tin[v];
	if(r < l) swap(r, l);  
	int bit = __lg(r - l + 1); 
	return hg(lca[bit][l], lca[bit][r - (1 << bit) + 1]); 
}
int get_dis(int u, int v) { 
	return dep[u] + dep[v] - 2 * dep[get_lca(u, v)];
}

signed main() { 
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0); 
	
	cin >> n; 
	fori(i, 2, n) { 
		int u, v; 
		cin >> u >> v;
		g[u].eb(v); 
		g[v].eb(u); 
	}
	
	dfs_sz(1, 1); 
	int cen = get_cen(1, 1); 
	
	dfs_prep(cen, cen); 
//	cout << cen << endl; 
	
	
	fori(bit, 0, 20) { 
		fori(i, 1, tim - (1 << bit) + 1) {
			lca[bit][i] = !bit? euler[i]: hg(lca[bit - 1][i], lca[bit - 1][i + (1 << bit - 1)]); 
		}
	}
	
//	cout << get_dis(1, 5) << endl; 
	
	fori(i, 1, n) nodes_sz[sz[i]].eb(i);
	
	Dia = make_pair(0, ii(cen, cen)); 
	
	int pt = n; 
	ford(j, n, 1) { 
		if(j & 1) ans[j] = 1; 
		else { 
			for(; pt >= j / 2; pt--) {
				for(int u: nodes_sz[pt]) {
//					cout << pt << ": " << u << endl; 
					int l = Dia.se.fi, r = Dia.se.se; 
					Dia = max({Dia, make_pair(get_dis(l, u), ii(l, u)), make_pair(get_dis(u, r), ii(u, r))}); 
				}
			}
			ans[j] = 1 + Dia.fi; 
		}
	}
	fori(i, 1, n) cout << ans[i] << endl; 
}

Compilation message (stderr)

meetings2.cpp: In function 'int main()':
meetings2.cpp:95:81: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   95 |    lca[bit][i] = !bit? euler[i]: hg(lca[bit - 1][i], lca[bit - 1][i + (1 << bit - 1)]);
      |                                                                             ~~~~^~~

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