oj.uz

Submission #151828

# Submission time Handle Problem Language Result Execution time Memory
151828 2019-09-05T04:44:24 Z balbit Network (BOI15_net) C++11
0 / 100
 13 ms 12084 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
#define ll long long 
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define FOR(i,a,b) for (int i=(a); i<(b); i++)
#define REP(i,n) for (int i=0; i<(n); i++)
#define RREP(i,n) for (int i=(n-1); i>=0; i--)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MNTO(a,b) a = min(a,(__typeof__(a))(b))
#define MXTO(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define debug(x) cerr<<#x<<" is "<<x<<endl
using namespace std;

#define int ll

const int iinf = 1<<29;
const ll inf = 1ll<<60;
const ll mod = 1e9+7;


void GG(){cout<<"No\n"; exit(0);}

ll mpow(ll a, ll n){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mod;
        a = a*a %mod;
        n>>=1;
    }
    return re;
}

ll inv (ll b){
    if (b==1) return b;
    return (mod-mod/b) * inv(mod%b) % mod;
}

const int maxn = 5e5+5;
vector<vector<int> > g(maxn);
int indeg [maxn];
vector<int> lf;
bool seen[maxn];

void dfs(int v){
    seen[v] = 1;
    if (indeg[v]==1) lf.pb(1+v);
    for (int u : g[v]){
        if (!seen[u]){
            dfs(u);

        }
    }
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n; cin>>n;
    
    REP(i,n-1){
        int a, b; cin>>a>>b;
        a--; b--; g[a].pb(b); g[b].pb(a); 
        indeg[a]++; indeg[b]++;
    }

    dfs(0);
    cout<<(SZ(lf)+1)/2<<endl;
    REP(i,SZ(lf)/2){
        cout<<lf[i]<<' '<<lf[SZ(lf) - i - 1]<<'\n';
    }
    if (SZ(lf) &1){
        cout<<lf[(SZ(lf))/2]<<' '<<lf[0]<<'\n';
    }
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12024 KB Output is correct
2 Incorrect 12 ms 12084 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12024 KB Output is correct
2 Incorrect 12 ms 12084 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12024 KB Output is correct
2 Incorrect 12 ms 12084 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -