QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#61197#3067. Justified Junglechiranko#TL 0ms0kbC++141.2kb2022-11-11 14:18:342022-11-11 14:18:37

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-11 14:18:37]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2022-11-11 14:18:34]
  • 提交

answer

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long LL;

const int maxn = 2e6 + 5;

int fl, n;

LL siz[maxn];
int tot, now;
int A[maxn], fa[maxn];
int h[maxn], to[maxn << 1], last[maxn << 1];

void add_edge(int x, int y)
{
	to[++tot] = y, last[tot] = h[x], h[x] = tot;
}

int dfs(int x, int fr)
{
	A[++now] = x;
	fa[x] = fr;
	for(int i = h[x]; i; i = last[i]){
		int v = to[i];
		if(v == fr)
			continue;
		dfs(v, x);
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for(int i = 1; i < n; ++i){
		int a, b;
		cin >> a >> b;
		add_edge(a, b), add_edge(b, a);
	}
	
	dfs(1, 0);
	vector<int> ans;
	for(int i = 1; i <= n; ++i){
		if(!(n % (i + 1))){
			int nd = n / (i + 1);
			fl = 1;
			for(int i = n ; i >= 1; --i){
				siz[A[i]] = 1;
				for(int j = h[A[i]]; j; j = last[j])
					siz[A[i]] += (to[j] == fa[A[i]]) ? 0 : siz[to[j]];
				if(siz[A[i]] > nd){
					fl = 0;
					break;
				}
				else{
					siz[A[i]] = siz[A[i]] == nd ? 0 : siz[A[i]];
				}
			}
			if(fl)
				ans.pb(i);
		}
	}
	
	for(int i = 0; i < ans.size(); ++i){
		cout << ans[i];
		if(i != ans.size() - 1)
			cout << " ";
	}
	return 0;
	
}

详细

Test #1:

score: 0
Time Limit Exceeded

input:

8
1 2
2 3
1 4
4 5
6 7
8 3
7 3

output:


result: