Submission #477099

#	Time	Username	Problem	Language	Result	Execution time	Memory
477099		EIMONIM	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	552 ms	42516 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define x first
#define y second
#define pb push_back
#define loop(i,s,e) for(int i=(s);i<(e);i++)
#define loopr(i,s,e) for(int i=(e)-1;i>=(s);i--)
#define chkmax(a,b) a = max(a,b)
#define chkmin(a,b) a = min(a,b)
#define all(x) x.begin(),x.end()
const int INF = 1e9, MOD = 1e9 + 7;

template <class A, class B> pair<A,B> operator+(pair<A,B>& a, pair<A,B>& b) {
    return {a.x+b.x, a.y+b.y}; }
template <class A, class B> pair<A,B> operator-(pair<A,B>& a, pair<A,B>& b) {
    return {a.x-b.x, a.y-b.y}; }
template <class A, class B> istream& operator>>(istream& is, pair<A,B>& a) {
    return is >> a.x >> a.y; }
template <class A, class B> ostream& operator << (ostream& os, const pair<A,B>& a) {
    return os << "< " << a.x << " , " << a.y << " >"; }

template<class T> ostream &operator<<(ostream &os, vector<T> v) { os << '['; if (!v.empty()) { os << v[0]; loop(i, 1, v.size()) os << ',' << v[i]; } return os << ']'; }
template<class T> ostream &operator<<(ostream &os, set<T> v) { os << '{'; if (!v.empty()) { os << *v.begin(); for(auto it = ++v.begin(); it != v.end(); ++it) os << ',' << *it; } return os << '}'; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
auto DIST = uniform_int_distribution<int>(0, INF);


int n;
vi sz;
vvi g;
vi ans;
vvi dp;
int dfssz(int cur, int p=-1){
	for(int nei:g[cur]) if(nei!=p) sz[cur]+=dfssz(nei, cur);
	return ++sz[cur];
}
int cent(int cur, int p=-1){
	for(int nei:g[cur]) if(nei!=p && 2*sz[nei]>=n) return cent(nei, cur);
	return cur;
}
void merge(int a, int b, int curd){
	if (dp[a].size()<dp[b].size()) swap(dp[a], dp[b]);
	loop(i,1,dp[b].size()){
		chkmax(ans[2*i], dp[a][i] + dp[b][i] - 2 * curd+1);
		chkmax(dp[a][i], dp[b][i]);
	}
	loop(i,1,dp[b].size()) dp[a].pb(curd);
}
void dfs(int cur, int p=-1, int d=0){
	vii ch;
	for(int nei:g[cur]) if(nei!=p){
		dfs(nei, cur, d+1);
		ch.pb({dp[nei].size(), nei});
	}
	sort(all(ch));
	dp[cur] = {-1, d};
	for(auto c:ch) merge(cur, c.y, d);
}
int32_t main(int argc, char *argv[]){
    ios_base::sync_with_stdio(false);
	cin >> n; g = vvi(n);
	loop(i,1,n){
		int a,b; cin>>a>>b; a--, b--;
		g[a].pb(b), g[b].pb(a);
	}
	sz = vi(n);
	dfssz(0);
	int r = cent(0);
	ans = vi(n+1,1), dp = vvi(n);
	dfs(r);
	loop(i,1,n+1) cout<<ans[i]<<endl;
    return 0;
}
/*
color a
cls
g++ sol.cpp -o a & a
5
1 2
2 3
4 2
3 5


*/ 

Compilation message (stderr)

meetings2.cpp: In function 'void merge(int, int, int)':
meetings2.cpp:13:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define loop(i,s,e) for(int i=(s);i<(e);i++)
      |                                    ^
meetings2.cpp:51:2: note: in expansion of macro 'loop'
   51 |  loop(i,1,dp[b].size()){
      |  ^~~~
meetings2.cpp:13:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define loop(i,s,e) for(int i=(s);i<(e);i++)
      |                                    ^
meetings2.cpp:55:2: note: in expansion of macro 'loop'
   55 |  loop(i,1,dp[b].size()) dp[a].pb(curd);
      |  ^~~~

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