Submission #734218

#	Time	Username	Problem	Language	Result	Execution time	Memory
734218		shoryu386	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	3 ms	5012 KiB

meetings2

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

#define int long long
#define MAXN 200007

vector<int> adjList[MAXN];
int d1[MAXN];

void dfs_diam1(int idx, int depth, int par){
	d1[idx] = depth;
	for (int x : adjList[idx]){
		if (x!=par) dfs_diam1(x, depth+1, idx);
	}
}

int d2[MAXN];
int arr[MAXN];
int weight[MAXN];
int par[MAXN];
int arrLen;
set<int> HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH;
void dfs_diam2(int idx, int depth, int parent){
	d2[idx] = depth;
	par[idx] = parent;
	for (int x : adjList[idx]){
		if (x!=parent) dfs_diam2(x, depth+1, idx);
	}
}

int dfs_fu(int idx, int par){
	int ans = 1;
	for (int x : adjList[idx]){
		if (x!=par) ans += dfs_fu(x, idx);
	}
	return ans;
}

main(){
	int n; cin >> n; int a, b;
	for (int x = 0; x < n-1; x++){
		cin >> a >> b; a--; b--; adjList[a].push_back(b); adjList[b].push_back(a);
	}
	
	dfs_diam1(0, 0, -1);
	
	int deepest = -1, deepestNode = 0;
	for (int x = 0; x < n; x++){
		if (d1[x] > deepest) deepest = d1[x], deepestNode = x;
	}
	
	dfs_diam2(deepestNode, 0, -1);
	int diam1 = deepestNode;
	
	deepest = -1, deepestNode = 0;
	for (int x = 0; x < n; x++){
		if (d2[x] > deepest) deepest = d2[x], deepestNode = x;
	}
	
	int diam2 = deepestNode;
	
	//we have the two ends of diameter
	
	//we root based on the first end
	
	int curNode = diam2;
	arrLen = d2[diam2] + 1;
	while (true){
		arr[d2[curNode]] = curNode;
		HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH.insert(curNode);
		if (d2[curNode] != 0) curNode = par[curNode];
		else break;
	}
	
	for (int x = 0; x < arrLen; x++){
		weight[x] = 1;
		for (int y : adjList[arr[x]]){
			if (HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH.count(y) == 0){
				weight[x] += dfs_fu(y, arr[x]);
			}
		}
	}
	
	//for (int x = 0; x < arrLen; x++) cout << arr[x] << ' ';
	//cout << '\n';
	//for (int x = 0; x < arrLen; x++) cout << weight[x] << ' ';
	//cout << '\n';
	
	//now we're done with preprocessing
	//aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
	
	//if odd, ans = 1
	//otherwise, we have to pick elements on the left and right such that their sum >= cur
	
	int l = -1, r = arrLen;
	int lsum = 0, rsum = 0;
	for (int x = 1; x <= n; x ++){
		//shift left ptr, right ptr
		if (x % 2 == 0){
			while (lsum < x/2){
				lsum += weight[l+1];
				l++;
			}
			
			while (rsum < x/2){
				rsum += weight[r-1];
				r--;
			}
			
			//int bonus = 0;
			//if (lsum > x/2) bonus++;
			//if (rsum > x/2) bonus++;
			
			cout << max(1LL, r-l+1) << '\n';
			//cerr << l << ' ' << r << "!!!\n";
		}
		else{
			cout << 1 << '\n';
		}
	}
	
	
	
	
	
	
	
	
	
}

Compilation message (stderr)

meetings2.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   39 | main(){
      | ^~~~
meetings2.cpp: In function 'int main()':
meetings2.cpp:53:6: warning: unused variable 'diam1' [-Wunused-variable]
   53 |  int diam1 = deepestNode;
      |      ^~~~~

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