oj.uz

답안 #58618

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
58618 2018-07-18T13:20:51 Z SpeedOfMagic Network (BOI15_net) C++17
0 / 100
 16 ms 12620 KB 
/** MIT License Copyright (c) 2018 Vasilyev Daniil **/
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
template<typename T> using v = vector<T>;
#define int long long
typedef string str;
typedef vector<int> vint;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
#define pb push_back
#define sz(a) ((int) a.size())
const long long inf = 4611686018427387903; //2^62 - 1
#if 0  //FileIO
const string fileName = "";
ifstream fin ((fileName == "" ? "input.txt"  : fileName + ".in" ));
ofstream fout((fileName == "" ? "output.txt" : fileName + ".out"));
#define get fin>>
#define put fout<<
#else
#define get cin>>
#define put cout<<
#endif
#define eol put endl
void read() {}     template<typename Arg,typename... Args> void read (Arg& arg,Args&... args){get (arg)     ;read(args...) ;}
void print(){}     template<typename Arg,typename... Args> void print(Arg  arg,Args...  args){put (arg)<<" ";print(args...);}
void debug(){eol;} template<typename Arg,typename... Args> void debug(Arg  arg,Args...  args){put (arg)<<" ";debug(args...);}
int getInt(){int a; get a; return a;}
//code goes here
const int N = 5e5 + 1;
v<pair<int, int>> leaves;
vint g[N];
void dfs(int cur = 1, int p = -1, int h = 0) {
    if (sz(g[cur]) == 1)
        leaves.pb({h, cur});
    for (int i : g[cur])
        if (i != p)
            dfs(i, cur, h + 1);
}
void run() {
    int n;
    get n;
    n++;
    rep(i, 2, n) {
        int v, u;
        read(v, u);
        g[v].pb(u);
        g[u].pb(v);
    }
    dfs();

    put sz(leaves) / 2 + sz(leaves) % 2;
    eol;

    sort(leaves.begin(), leaves.end());

    int p1 = 0, p2 = sz(leaves) - 1;
    while (p1 < p2) {
        print(leaves[p1].second, leaves[p2].second);
        eol;
        p1++;
        p2--;
    }

    if (sz(leaves) % 2) {
        print(leaves[p1].second);
        rep(i, 1, n)
            if (leaves[p1].second != i && g[leaves[p1].second][0] != i) {
                print(i);
                eol;
                return;
            }
    }
}

int32_t main() {srand(time(0)); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); put fixed; put setprecision(15); run(); return 0;}

Subtask #1
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 12280 KB Output is correct
2 Correct 16 ms 12280 KB Output is correct
3 Correct 15 ms 12368 KB Output is correct
4 Correct 16 ms 12420 KB Output is correct
5 Correct 16 ms 12420 KB Output is correct
6 Correct 14 ms 12620 KB Output is correct
7 Correct 12 ms 12620 KB Output is correct
8 Correct 15 ms 12620 KB Output is correct
9 Correct 16 ms 12620 KB Output is correct
10 Correct 15 ms 12620 KB Output is correct
11 Incorrect 13 ms 12620 KB Breaking single line is causing network to disconnect.
12 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 12280 KB Output is correct
2 Correct 16 ms 12280 KB Output is correct
3 Correct 15 ms 12368 KB Output is correct
4 Correct 16 ms 12420 KB Output is correct
5 Correct 16 ms 12420 KB Output is correct
6 Correct 14 ms 12620 KB Output is correct
7 Correct 12 ms 12620 KB Output is correct
8 Correct 15 ms 12620 KB Output is correct
9 Correct 16 ms 12620 KB Output is correct
10 Correct 15 ms 12620 KB Output is correct
11 Incorrect 13 ms 12620 KB Breaking single line is causing network to disconnect.
12 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 12280 KB Output is correct
2 Correct 16 ms 12280 KB Output is correct
3 Correct 15 ms 12368 KB Output is correct
4 Correct 16 ms 12420 KB Output is correct
5 Correct 16 ms 12420 KB Output is correct
6 Correct 14 ms 12620 KB Output is correct
7 Correct 12 ms 12620 KB Output is correct
8 Correct 15 ms 12620 KB Output is correct
9 Correct 16 ms 12620 KB Output is correct
10 Correct 15 ms 12620 KB Output is correct
11 Incorrect 13 ms 12620 KB Breaking single line is causing network to disconnect.
12 Halted 0 ms 0 KB -