oj.uz

답안 #911148

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
911148 2024-01-18T13:39:21 Z ttamx Network (BOI15_net) C++14
0 / 100
 8 ms 25264 KB 
#include<bits/stdc++.h>

using namespace std;

const int N=5e5+5;

int n;
int sz[N];
vector<int> adj[N],vec[N];

int dfssz(int u,int p=0){
    sz[u]=(adj[u].size()<2);
    for(auto v:adj[u])if(v!=p)sz[u]+=dfssz(v,u);
    return sz[u];
}

int centroid(int u,int cnt,int p=0){
    for(auto v:adj[u])if(v!=p&&sz[v]>cnt/2)return centroid(v,cnt,u);
    return u;
}

void dfs(int u,int p,vector<int> &comp){
    if(adj[u].size()==1)comp.emplace_back(u);
    for(auto v:adj[u])if(v!=p)dfs(v,u,comp);
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for(int i=1;i<n;i++){
        int u,v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    int c=centroid(1,dfssz(1));
    vector<vector<int>> res;
    for(auto v:adj[c]){
        res.push_back({});
        dfs(v,c,res.back());
    }
    for(int i=0;i<res.size();i++)vec[res[i].size()].emplace_back(i);
    vector<pair<int,int>> ans;
    int p=0;
    for(int i=n;i>=1;i--){
        for(auto x:vec[i]){
            if(p){
                ans.emplace_back(p,res[x].back());
                p=0;
            }else{
                p=res[x].back();
            }
            res[x].pop_back();
            vec[i-1].emplace_back(x);
        }
    }
    if(p)ans.emplace_back(p,c);
    cout << ans.size() << "\n";
    for(auto [x,y]:ans)cout << x << " " << y << "\n";
}

Compilation message

net.cpp: In function 'int main()':
net.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i=0;i<res.size();i++)vec[res[i].size()].emplace_back(i);
      |                 ~^~~~~~~~~~~
net.cpp:59:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |     for(auto [x,y]:ans)cout << x << " " << y << "\n";
      |              ^

Subtask #1
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 25180 KB Output is correct
2 Correct 7 ms 25180 KB Output is correct
3 Correct 8 ms 25180 KB Output is correct
4 Correct 8 ms 25264 KB Output is correct
5 Correct 7 ms 25180 KB Output is correct
6 Correct 7 ms 25180 KB Output is correct
7 Correct 7 ms 25180 KB Output is correct
8 Incorrect 6 ms 25228 KB Breaking single line is causing network to disconnect.
9 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 25180 KB Output is correct
2 Correct 7 ms 25180 KB Output is correct
3 Correct 8 ms 25180 KB Output is correct
4 Correct 8 ms 25264 KB Output is correct
5 Correct 7 ms 25180 KB Output is correct
6 Correct 7 ms 25180 KB Output is correct
7 Correct 7 ms 25180 KB Output is correct
8 Incorrect 6 ms 25228 KB Breaking single line is causing network to disconnect.
9 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 25180 KB Output is correct
2 Correct 7 ms 25180 KB Output is correct
3 Correct 8 ms 25180 KB Output is correct
4 Correct 8 ms 25264 KB Output is correct
5 Correct 7 ms 25180 KB Output is correct
6 Correct 7 ms 25180 KB Output is correct
7 Correct 7 ms 25180 KB Output is correct
8 Incorrect 6 ms 25228 KB Breaking single line is causing network to disconnect.
9 Halted 0 ms 0 KB -