oj.uz

Submission #734227

# Submission time Handle Problem Language Result Execution time Memory
734227 2023-05-02T05:33:01 Z shoryu386 Meetings 2 (JOI21_meetings2) C++17
0 / 100
 4 ms 5016 KB 
#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);
	}
	
	int ans[n+3];
	for (int x = 0; x <= n; x++) ans[x] = LONG_LONG_MAX/100;
	
	for (int start = 0; start < n; start++){
		dfs_diam1(start, start, -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++;
				
				ans[x] = min(ans[x], max(1LL, r-l+1 + bonus));
				//cerr << l << ' ' << r << "!!!\n";
			}
			else{
				ans[x] = 1;
			}
		}
	}
	for (int x = 1; x <= n; x++) cout << ans[x] << '\n';
	
	
	
	
	
	
	
	
}

Compilation message

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:57:7: warning: unused variable 'diam1' [-Wunused-variable]
   57 |   int diam1 = deepestNode;
      |       ^~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 5016 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Incorrect 3 ms 4948 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 5016 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Incorrect 3 ms 4948 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 5016 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Incorrect 3 ms 4948 KB Output isn't correct
7 Halted 0 ms 0 KB -