QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#61197 | #3067. Justified Jungle | chiranko# | TL | 0ms | 0kb | C++14 | 1.2kb | 2022-11-11 14:18:34 | 2022-11-11 14:18:37 |
Judging History
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