Submission #1181294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181294		KK_1729	Meetings 2 (JOI21_meetings2)	C++20	100 / 100	811 ms	48012 KiB

meetings2

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

// #define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<int> a){
	for (auto x: a) cout << x << " ";
	cout << endl;
}
vector<vector<int>> graph;
vector<int> subtree, subtree1;
vector<int> vis;
int dp(int x, int p = -1){
    if (vis[x]) return 0;
    subtree[x] = 1;
    for (auto node: graph[x]){
        if (node == p) continue;
        subtree[x] += dp(node, x);
    }
    return subtree[x];
}
int find_centroid(int x, int p, int n){
    for (auto node: graph[x]){
        if (node == p) continue;
        if (!vis[node] && subtree[node]*2 > n) return find_centroid(node, x, n);
    }
    return x;
}
vector<int> curr;
vector<int> o;
vector<int> depth;
int dp1(int x, int p = -1, int e = 0){
	if (vis[x]) return 0;
	o[x] = e;
	curr.pb(x);
	subtree1[x] = 1;
	for (auto node: graph[x]){
		if (node == p) continue;
		depth[node] = depth[x]+1;
		subtree1[x] += dp1(node, x, e);
	}
	return subtree1[x];
}
vector<int> answer;
void init_centroid(int x = 1, int p = -1){
    dp(x);
    int c = find_centroid(x, -1, subtree[x]);
    // cout << c << endl;
    vector<int> candidates;
    for (auto item: graph[c]){
    	if (!vis[item]) candidates.pb(item);
    }
    for (auto d: candidates){
        depth[d] = 1;
    	dp1(d, c, d);
    }
    vector<vector<int>> opt;
    for (auto item: curr){
    	opt.pb({subtree1[item], depth[item], o[item]});
    }
    sort(all(opt));
    reverse(all(opt));
    map<int, int> e;
   	multiset<int, greater<int>> k;
   	for (auto item: candidates){
   		e[item] = 0;
   		k.insert(0);
   	}
   	k.insert(0);
   	k.insert(0);
   	int ind = 0;
   	int at = curr.size()+1;
   	if (at%2 == 1) at--;
   	while (at > 0){
   	    while (ind < opt.size() && opt[ind][0] >= at/2){
   	        vector<int> op = opt[ind];
       		k.erase(k.find(e[op[2]]));
       		e[op[2]] = max(e[op[2]], op[1]);
       		k.insert(e[op[2]]);
       		ind++;
   	    }
   		auto t = k.begin();
   		int s = *t;
   		t++;
   		s += *t;
   		answer[at] = max(answer[at], s+1);
   		at -= 2;
   	}

    for (auto x: curr){
    	subtree[x] = 0;
    	o[x] = 0;
    	depth[x] = 0;
    }
    e.clear();
    k.clear();

    vis[c] = 1;
    // ctree[c] = p;
 	curr.clear();
    for (int node: graph[c]){
        if (!vis[node]){
            init_centroid(node, c);
        }
    }
}
void solve(){
	int n; cin >> n;
	graph.resize(n+1);
	subtree.resize(n+1);
	subtree1.resize(n+1);
	o.resize(n+1);
	vis.resize(n+1);
	answer.resize(n+5);
	depth.resize(n+1);

	FOR(i,0,n-1){
		int u, v; cin >> u >> v;

		graph[u].pb(v);
		graph[v].pb(u);
	}
	init_centroid(1);
	for (int i = 1; i <= n; ++i){
	    if (i%2 == 1) cout << 1 << endl;
	    else{
	        cout << answer[i] << endl;
	    }
	}
}


int32_t main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);
	int t = 1; // cin >> t;
	while (t--) solve();
}

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