oj.uz

답안 #551719

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
551719 2022-04-21T11:27:09 Z GioChkhaidze Meetings 2 (JOI21_meetings2) C++14
0 / 100
 19 ms 29224 KB 
#include <bits/stdc++.h>

#define pb push_back
#define f first
#define s second

using namespace std;

const int N = 2e5 + 5;

int n;
int timer, in[N], out[N], dep[N], tot[N], ans[N], P[N][20];
vector < int > v[N];
set < int > st[N];

bool is_anc(int a, int b) {
	return (in[a] <= in[b] && out[b] <= out[a]);
}

int LCA(int a, int b) {
	if (dep[a] > dep[b]) swap(a, b);
	if (is_anc(a, b)) return a;
	for (int j = 18; j >= 0; --j) 
		if (!is_anc(P[a][j], b)) a = P[a][j];
	return P[a][0];
}

int dst(int a, int b) {
	return dep[a] + dep[b] - 2 * dep[LCA(a, b)] + 1;
}

void dfs(int x, int p) {
	dep[x] = dep[p] + 1;
	in[x] = ++timer;
	P[x][0] = p;
	for (int j = 1; j <= 18; ++j) {
		P[x][j] = P[P[x][j - 1]][j - 1];
	}
	for (int i = 0; i < v[x].size(); ++i) {
		int to = v[x][i];
		if (to == p) continue;
		dfs(to, x);
	}
	out[x] = timer;
}

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	for (int i = 1; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		v[a].pb(b);
		v[b].pb(a);
		st[a].insert(b);
		st[b].insert(a);
	}
	
	dfs(1, 1);
	queue < int > q;
	for (int i = 1; i <= n; ++i) {
		tot[i] = 1;
		if (v[i].size() == 1) {
			q.push(i);
		}
	}
	
	vector < pair < int , int > > rec;
	while (q.size()) {
		int x = q.front();
		q.pop();
		if (st[x].size() == 1) {
			int y = (*st[x].begin());
			rec.pb({x, tot[x]});
			tot[y] += tot[x];
			st[y].erase(x);
			st[x].erase(y);
			if (st[y].size() == 1) {
				q.push(y);
			}
		}
	}
	
	for (int i = 0; i + 1 < rec.size(); ++i) {
		assert(rec[i].s <= rec[i + 1].s);
	}
	
	int str = 1;
	for (int i = 1; i <= n; ++i) {
		if (tot[i] == n) str = i;
	}
	
	int a0 = str, b0 = str, dm = 1;
	for (int i = n; i >= 1; --i) {
		if (i % 2 == 1) {
			ans[i] = 1;
		}
			else {
			while (rec.size() && rec.back().s >= i / 2) {
				int x = rec.back().f, a1 = dst(a0, x), b1 = dst(b0, x);
				rec.pop_back();
				if (a1 <= b1) {
					if (dm < b1) dm = b1, a0 = x;
				}
					else 
				if (b1 < a1) {
					if (dm < a1) dm = a1, b0 = x;
				}
			}
			ans[i] = dm;		
		}
	}
	
	for (int i = 1; i <= n; ++i) {
		cout << ans[i] << "\n";
	} 
}

Compilation message

meetings2.cpp: In function 'void dfs(int, int)':
meetings2.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for (int i = 0; i < v[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
meetings2.cpp: At global scope:
meetings2.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main () {
      | ^~~~
meetings2.cpp: In function 'int main()':
meetings2.cpp:85:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  for (int i = 0; i + 1 < rec.size(); ++i) {
      |                  ~~~~~~^~~~~~~~~~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14432 KB Output is correct
4 Runtime error 19 ms 29224 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14432 KB Output is correct
4 Runtime error 19 ms 29224 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14432 KB Output is correct
4 Runtime error 19 ms 29224 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -