QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#85197#3100. Meetings 2lmeowdn0 13ms27228kbC++141.6kb2023-03-07 09:52:592023-03-07 09:53:00

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-07 09:53:00]
  • 评测
  • 测评结果：0
  • 用时：13ms
  • 内存：27228kb
查看
  • [2023-03-07 09:52:59]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define fi first
#define se second
#define eb emplace_back
#define popc __builtin_popcount
#define sgn(x) ((x)&1?-1:1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef unsigned long long ull;
typedef long double ld;

int read() {
    int x=0,w=1; char c=getchar(); 
    while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
    while(isdigit(c)) {x=x*10+c-'0'; c=getchar();}
    return x*w;
}

const int N=1e6+9;
int n,a[N],d[N],sz[N],cnt,ans[N],msz[N],rt,tp,g[N],mx[N];
vi e[N];

void dfs(int u,int fa,int tp) {
    sz[u]=1;
    for(int v:e[u]) if(v!=fa) d[v]=d[u]+1, dfs(v,u,tp), sz[u]+=sz[v], msz[u]=max(msz[u],sz[v]);
    msz[u]=max(msz[u],n-sz[u]);
    if(tp&&(!rt||msz[u]<msz[rt])) rt=u;
}
void dfs2(int u,int fa) {
    g[sz[u]]=max(g[sz[u]],d[u]);
    for(int v:e[u]) if(v!=fa) dfs2(v,u);
}

signed main() {
    n=read();
    rep(i,2,n) {
        int u=read(), v=read();
        e[u].eb(v), e[v].eb(u);
    }
    dfs(1,0,1); d[rt]=0;
    dfs(rt,0,0);
    rep(i,1,n) ans[i]=1;
    int msz=0;
    for(int u:e[rt]) {
        rep(i,1,sz[u]+1) g[i]=0;
        dfs2(u,rt);
        per(i,sz[u],1) g[i]=max(g[i],g[i+1]);
        rep(k,1,min(msz,sz[u])) ans[2*k]=max(ans[2*k],g[k]+mx[k]+1);
        rep(k,1,min(sz[u],n-sz[u])) ans[2*k]=max(ans[2*k],g[k]+1);
        msz=max(sz[u],msz);
        rep(i,1,sz[u]) mx[i]=max(mx[i],g[i]);
    }
    rep(i,1,n) printf("%lld\n",ans[i]);
    return 0;
}
源文件, 语言: C++14

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 4
Accepted
time: 10ms
memory: 27216kb

input:

1

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 5ms
memory: 27016kb

input:

2
2 1

output:

1
2

result:

ok 2 lines

Test #3:

score: 0
Accepted
time: 12ms
memory: 27052kb

input:

3
1 3
3 2

output:

1
3
1

result:

ok 3 lines

Test #4:

score: 0
Accepted
time: 8ms
memory: 26996kb

input:

14
12 14
12 9
14 2
12 6
12 7
6 4
3 4
1 4
12 8
13 1
10 12
11 6
6 5

output:

1
7
1
5
1
3
1
3
1
2
1
2
1
2

result:

ok 14 lines

Test #5:

score: 0
Accepted
time: 8ms
memory: 26968kb

input:

14
10 14
3 10
14 13
1 3
3 5
3 11
12 14
14 6
11 8
2 3
7 8
9 7
1 4

output:

1
8
1
6
1
5
1
4
1
2
1
1
1
1

result:

ok 14 lines

Test #6:

score: 0
Accepted
time: 4ms
memory: 27072kb

input:

14
8 13
13 10
13 7
6 8
5 7
10 4
9 5
12 8
6 2
4 11
5 1
9 3
4 14

output:

1
8
1
6
1
5
1
4
1
2
1
1
1
1

result:

ok 14 lines

Test #7:

score: 0
Accepted
time: 4ms
memory: 27048kb

input:

14
9 2
9 8
3 8
14 9
13 3
1 2
5 2
9 6
4 2
4 11
10 6
12 10
7 9

output:

1
7
1
5
1
3
1
2
1
2
1
1
1
1

result:

ok 14 lines

Test #8:

score: 0
Accepted
time: 11ms
memory: 27024kb

input:

15
10 7
15 7
14 7
15 11
6 15
10 8
14 2
4 8
15 1
3 6
4 13
1 9
5 2
8 12

output:

1
8
1
6
1
4
1
4
1
3
1
2
1
1
1

result:

ok 15 lines

Test #9:

score: 0
Accepted
time: 7ms
memory: 27020kb

input:

16
11 8
11 10
10 1
11 2
15 8
13 10
9 2
2 4
8 6
2 7
3 7
12 9
6 16
9 14
12 5

output:

1
8
1
6
1
4
1
4
1
2
1
2
1
2
1
2

result:

ok 16 lines

Test #10:

score: 0
Accepted
time: 3ms
memory: 27068kb

input:

16
7 11
16 11
11 6
1 16
1 14
1 3
12 3
14 8
12 10
5 16
6 9
6 4
9 2
15 4
2 13

output:

1
10
1
8
1
6
1
4
1
4
1
4
1
2
1
2

result:

ok 16 lines

Test #11:

score: 0
Accepted
time: 13ms
memory: 27048kb

input:

16
13 3
16 13
16 5
16 8
3 12
11 16
14 8
15 12
3 10
10 2
16 1
6 10
11 9
8 4
1 7

output:

1
7
1
5
1
5
1
3
1
3
1
3
1
2
1
1

result:

ok 16 lines

Test #12:

score: 0
Accepted
time: 3ms
memory: 27004kb

input:

16
12 13
13 3
14 3
7 14
9 3
11 13
14 8
2 14
14 6
2 16
4 3
7 5
16 1
9 10
13 15

output:

1
7
1
5
1
4
1
3
1
2
1
2
1
2
1
2

result:

ok 16 lines

Test #13:

score: 0
Accepted
time: 4ms
memory: 27228kb

input:

16
1 7
15 1
8 1
15 12
7 2
1 13
13 14
12 3
3 16
11 3
9 3
10 12
2 5
6 7
9 4

output:

1
9
1
7
1
5
1
5
1
4
1
3
1
3
1
2

result:

ok 16 lines

Test #14:

score: 0
Accepted
time: 6ms
memory: 27044kb

input:

14
8 11
11 5
7 5
7 3
3 12
12 2
2 14
14 6
3 1
9 12
6 13
10 1
4 7

output:

1
10
1
8
1
6
1
4
1
3
1
2
1
1

result:

ok 14 lines

Test #15:

score: 0
Accepted
time: 1ms
memory: 27212kb

input:

14
6 8
9 8
1 9
1 3
3 10
5 10
13 5
11 13
11 12
12 14
7 14
4 7
4 2

output:

1
14
1
12
1
10
1
8
1
6
1
4
1
2

result:

ok 14 lines

Test #16:

score: 0
Accepted
time: 7ms
memory: 27056kb

input:

15
4 7
7 3
15 7
7 14
10 7
7 1
13 7
8 7
7 9
6 7
1 5
4 12
2 3
10 11

output:

1
5
1
3
1
1
1
1
1
1
1
1
1
1
1

result:

ok 15 lines

Test #17:

score: 0
Accepted
time: 2ms
memory: 26932kb

input:

16
14 7
15 14
14 5
14 2
14 12
11 14
13 14
14 10
3 14
14 9
14 16
14 6
1 14
14 8
4 14

output:

1
3
1
1
1
1
1
1
1
1
1
1
1
1
1
1

result:

ok 16 lines

Test #18:

score: 0
Accepted
time: 4ms
memory: 26988kb

input:

16
4 9
9 10
10 6
16 6
4 5
5 14
14 15
5 7
8 14
14 13
11 5
5 12
5 2
5 1
3 5

output:

1
8
1
6
1
5
1
4
1
2
1
1
1
1
1
1

result:

ok 16 lines

Test #19:

score: 0
Accepted
time: 4ms
memory: 27068kb

input:

15
4 15
4 10
1 4
5 4
4 12
14 4
11 4
4 13
13 9
6 9
6 7
2 13
2 8
3 2

output:

1
6
1
4
1
3
1
2
1
2
1
2
1
2
1

result:

ok 15 lines

Test #20:

score: 0
Accepted
time: 3ms
memory: 27220kb

input:

16
1 2
2 5
12 2
2 15
14 2
2 11
6 2
10 2
10 4
13 4
16 13
10 9
9 7
9 3
8 3

output:

1
7
1
5
1
3
1
3
1
2
1
2
1
2
1
2

result:

ok 16 lines

Test #21:

score: -4
Wrong Answer
time: 13ms
memory: 26992kb

input:

15
11 15
15 6
15 12
15 2
15 14
9 15
7 15
13 15
4 1
4 3
13 3
8 13
10 8
5 10

output:

1
6
1
4
1
3
1
2
1
2
1
2
1
2
1

result:

wrong answer 2nd lines differ - expected: '7', found: '6'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

服务器时间: 2024-12-02 16:02:58 | 开源项目