QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#61206 | #3067. Justified Jungle | chiranko# | TL | 0ms | 0kb | C++14 | 1.4kb | 2022-11-11 14:58:34 | 2022-11-11 14:58:36 |
Judging History
answer
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long LL;
const int maxn = 4e6 + 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);
}
}
inline int read(){
int x=0,f=1;char ch=' ';
while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return f==1?x:-x;
}
int main()
{
n = read();
for(int i = 1; i < n; ++i){
int a, b;
a = read(), b = read();
add_edge(a, b), add_edge(b, a);
}
assert(n==8);
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){
printf("%d", ans[i]);
if(i != ans.size() - 1)
printf(" ");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
8 1 2 2 3 1 4 4 5 6 7 8 3 7 3