oj.uz

Submission #915186

# Submission time Handle Problem Language Result Execution time Memory
915186 2024-01-23T12:57:50 Z 3as8 Village (BOI20_village) C++14
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>

#define ll long long
#define endl "\n"
#define fastIO cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false);

#define mid ((l + r) / 2)
#define lChild ((index * 2) + 1)
#define rChild ((index * 2) + 2)

using namespace std;

ll ans = 0;
bool dfs(vector<vector<ll> >& graph, vector<ll>& cur, ll startIndex, ll p) {


    bool hasLeaf = false;
    bool isLeaf = true;
    for(auto el : graph[startIndex]) {
        if(el == p) continue;

        hasLeaf &= dfs(graph, cur, el, startIndex);

        isLeaf = false;

    }

    if(isLeaf && cur[p] != startIndex ) {

        ans += 2;
        swap(cur[p], cur[startIndex]);

        return isLeaf;
    }

    if(cur[startIndex] == startIndex) {


        ans += 2;
        swap(cur[p], cur[startIndex]);
    }

    return isLeaf;
}


void solve(ll _) {

    ll n; cin>>n;

    vector<vector<ll> > graph(n);
    for(int i = 0; i < n - 1; i++) {
        ll x, y; cin>>x>>y;
        x--; y--;

        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    vector<bool> stat(n, true);
    vector<ll> curr(n);
    for(int i = 0; i < n; i++) curr[i] = i;

    dfs(graph, curr, 0, 0);

    cout<<ans<<" "<<2<<endl;
    for(auto el : curr) cout<<el + 1<<" ";
    cout<<endl;

    for(auto el : curr) cout<<el + 1<<" ";
    cout<<endl;
}

int main() {
    fastIO

    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);

    ll t = 0; solve(t);
}

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB Partially correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB Partially correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -