Submission #394625

#	Time	Username	Problem	Language	Result	Execution time	Memory
394625		Sara	Network (BOI15_net)	C++14	100 / 100	486 ms	45416 KiB

net

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long
#define F first
#define S second
#define pb push_back
#define md ((b + e) >> 1)

const ll N = 5e5 + 5;
const ll LOG = 17;
const ll INF = 1e9 + 5;
const ll MOD = 1e9 + 7;

/*int n, m;
char mat[N][N];
pair <int, int> L[N][N], R[N][N];
pair <int, int> U[N][N], D[N][N];
pair <int, int> dir[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
vector < pair <int, int> > g[N][N];
pair <int, int> st, en;

inline bool valid(int x, int y){
    return (1 <= x && x <= n && 1 <= y && y <= m && mat[x][y] == '.');;
}

inline void pre(){
    for (int i = 1; i <= n; i ++){
        for (int j = 1; j <= m; j ++){
            if (mat[i][j] == '#'){
                L[i][j] = {i, j};
                U[i][j] = {i, j};
            }
            else {
                L[i][j] = L[i][j - 1];
                U[i][j] = U[i - 1][j];
            }
        }
    }
    for (int i = n; i >= 1; i --){
        for (int j = m; j >= 1; j --){
            if (mat[i][j] == '#'){
                R[i][j] = {i, j};
                D[i][j] = {i, j};
            }
            else {
                R[i][j] = R[i][j + 1];
                D[i][j] = D[i + 1][j];
            }
        }
    }
    return;
}

int dis[N][N];
queue < pair <int, int> > q;
inline void bfs(){

    for (int i = 1; i <= n; i ++){
        for (int j = 1; j <= m; j ++){
            dis[i][j] = INF;
        }
    }

    q.push({st.F, st.S});
    while (q.size()){
        auto v = q.front();
        for (auto u : g[v.F][v.S]){
            if (dis[v.F][v.S] + 1 < dis[u.F][u.S]){
                dis[u.F][u.S] = dis[v.F][v.S] + 1;
                q.push(u);
            }
        }
    }

    cout << dis[en.F][en.S] << '\n';
    return;
}*/

int n;
int tim;
vector <int> g[N];
vector < pair <int, int> > leaf;
int root = 1;

void dfs(int v, int par = 0){

    tim ++;
    if ((int)g[v].size() == 1){
        leaf.pb({tim, v});
    }

    for (int u : g[v]){
        if (u != par){
            dfs(u, v);
        }
    }

    return;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 0; i < n - 1; i ++){
        int u, v;
        cin >> u >> v;
        g[u].pb(v); g[v].pb(u);
    }

    root = 1;
    while ((int)g[root].size() == 1){
        root ++;
    }

    dfs(root);
    sort(leaf.begin(), leaf.end());
    int ans = ((int)leaf.size() + 1) / 2;
    int nim = (int)leaf.size() / 2;

    cout << ans << '\n';
    for (int i = nim; i < (int)leaf.size(); i ++){
        cout << leaf[i - nim].S << ' ' << leaf[i].S << '\n';
    }

    /*cin >> n >> m;

    for (int i = 1; i <= n; i ++){
        for (int j = 1; j <= m; j ++){
            cin >> mat[i][j];
            if (mat[i][j] == 's'){
                st = {i, j};
                mat[i][j] = '.';
            }
            if (mat[i][j] == 'c'){
                en = {i, j};
                mat[i][j] = '.';
            }
        }
    }

    pre();

    for (int i = 1; i <= n; i ++){
        for (int j = 1; j <= m; j ++){
            for (int d = 0; d < 4; d ++){
                int x = i + dir[d].F;
                int y = j + dir[d].S;
                if (valid(x, y)){
                    g[i][j].pb({x, y});
                    g[x][y].pb({i, j};
                }
            }
        }
    }   

    bfs();*/
    
    return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 45 / 45
• Subtask 3: 37 / 37