QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#433017#3100. Meetings 2snpmrnhlol0 3ms8516kbC++142.7kb2024-06-07 22:23:582024-06-07 22:24:08

Judging History

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

  • [2024-06-07 22:24:08]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:8516kb
  • [2024-06-07 22:23:58]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5;
const int inf = 2e9;
vector <int> e[N];
int bad[N];
int sub[N];
int gbsub[N];
int pr[N];
int ans[N + 1];
int n;
void dfs(int node, int p){
    gbsub[node] = 1;
    pr[node] = p;
    for(auto i:e[node]){
        if(i == p)continue;
        dfs(i,node);
        gbsub[node]+=gbsub[i];
    }
}
int get(int node, int p){
    if(pr[node] == p){
        return gbsub[node];
    }else{
        return n - gbsub[p];
    }
}
void cendecomp(int node){
    vector <array<int,3>> nodes;
    int sz = 0;
    int cen = -1,cennr = inf;
    auto dfs = [&](auto self, int node, int p) -> void{
        sz++;
        for(auto i:e[node]){
            if(i == p || bad[i])continue;
            self(self, i, node);
        }
    };
    auto dfs2 = [&](auto self, int node, int p) -> void{
        sub[node] = 1;
        int mx = -1;
        for(auto i:e[node]){
            if(i == p || bad[i])continue;
            self(self, i, node);
            sub[node]+=sub[i];
            mx = max(mx,sub[i]);
        }
        mx = max(mx,sz - sub[node]);
        if(mx < cennr){
            mx = cennr;
            cen = node;
        }
    };
    auto dfs3 = [&](auto self, int node, int p, int dpth, int orig) -> void{
        int nr = min(get(node,p),get(cen,orig));
        ans[2*nr] = max(dpth,ans[2*nr]);
        for(auto i:e[node]){
            if(i == p || bad[i])continue;
            self(self, i, node, dpth + 1, orig);
        }
    };
    auto dfs4 = [&](auto self, int node, int p, int dpth, int orig) -> void{
        nodes.push_back({orig,dpth,get(node,p)});
        for(auto i:e[node]){
            if(i == p || bad[i])continue;
            self(self, i, node, dpth + 1, orig);
        }
    };
    dfs(dfs, node, -1);
    dfs2(dfs2, node, -1);
    for(auto i:e[cen]){
        if(bad[i])continue;
        dfs3(dfs3, i, cen, 2, i);
        dfs4(dfs4, i, cen, 1, i);
    }
    for(int i = 0;i < nodes.size();i++){
        for(int j = 0;j < nodes.size();j++){
            if(nodes[i][0] == nodes[j][0])continue;
            ans[min(nodes[i][2],nodes[j][2])] = max(ans[min(nodes[i][2],nodes[j][2])],nodes[i][1] + nodes[j][1]);
        }
    }
    bad[cen] = 1;
    for(auto i:e[cen]){
        if(bad[i])continue;
        cendecomp(i);
    }
}
void solve(){
    cin>>n;
    for(int i = 0;i < n - 1;i++){
        int u,w;
        cin>>u>>w;
        u--;w--;
        e[w].push_back(u);
        e[u].push_back(w);
    }
    dfs(0, -1);
    cendecomp(0);
    for(int i = 1;i <= n;i++){
        if(i%2 == 1)cout<<1<<'\n';
        else cout<<ans[i]<<'\n';
    }
}
int main(){
    int t;
    t = 1;
    while(t--)solve();
    return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 4
Accepted
time: 3ms
memory: 8516kb

input:

1

output:

1

result:

ok single line: '1'

Test #2:

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

input:

2
2 1

output:

1
2

result:

ok 2 lines

Test #3:

score: 4
Accepted
time: 3ms
memory: 8464kb

input:

3
1 3
3 2

output:

1
3
1

result:

ok 3 lines

Test #4:

score: 0
Wrong Answer
time: 3ms
memory: 8296kb

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
6
1
5
1
0
1
3
1
0
1
0
1
2

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%