oj.uz

Submission #897484

# Submission time Handle Problem Language Result Execution time Memory
897484 2024-01-03T07:52:34 Z Neco_arc Village (BOI20_village) C++17
0 / 100
 2 ms 8028 KB 
#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define VietAnh "Village"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 2e5 + 7

using namespace std;

const ll mod = 1e9 + 7;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll GetRandom(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r)(rng);
}

int n;
vector<int> edges[maxn];
int vt[maxn], used[maxn], a[maxn];
int child[maxn], cnt;
ll ans1, ans2;

void DFS(int u, int par)
{
    child[u] = 1, vt[++cnt] = u;
    for(int v : edges[u]){
        if(v == par) continue;
        DFS(v, u);

        child[u] += child[v];
        if(!used[v]) {
            used[u] = 1, swap(a[u], a[v]);
            ans2 += 2;
        }
    }

    if(u != 1) ans1 += min(child[u], n - child[u]) * 2;
    else if(!used[1]) ans2 += 2, swap(a[u], a[edges[1][0]]);

}

void solve()
{

    cin >> n;

    fi(i, 1, n - 1) {
        int x, y;
        cin >> x >> y;

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

    fi(i, 1, n) a[i] = i;
    DFS(1, 0);

    fi(i, n + 1, 2 * n) vt[i] = vt[i - n];

    cout << ans2 << '\n';
    fi(i, 1, n) cout << a[i] << " ";
    cout << '\n';

    cout << ans1 << '\n';
    fi(i, 1, n) cout << vt[i + (n / 2)] << " ";
}


int main()
{

    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(VietAnh".inp", "r")) {
        freopen(VietAnh".inp", "r", stdin);
        freopen(VietAnh".out", "w", stdout);
    }


    int nTest = 1;
//    cin >> nTest;

    while(nTest--)
    {
        solve();
    }


    return 0;
}

Compilation message

Village.cpp: In function 'int main()':
Village.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen(VietAnh".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Village.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen(VietAnh".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8024 KB Integer parameter [name=vi] equals to 8, violates the range [1, 4]
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8028 KB Integer parameter [name=vi] equals to 2186, violates the range [1, 256]
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8024 KB Integer parameter [name=vi] equals to 8, violates the range [1, 4]
2 Halted 0 ms 0 KB -