QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#433017 | #3100. Meetings 2 | snpmrnhlol | 0 | 3ms | 8516kb | C++14 | 2.7kb | 2024-06-07 22:23:58 | 2024-06-07 22:24:08 |
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%