Submission #897489

#	Time	Username	Problem	Language	Result	Execution time	Memory
897489		Neco_arc	Village (BOI20_village)	C++17	50 / 100	46 ms	20816 KiB

Village

#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 num[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;
    num[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[1], 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 << " " << ans1 <<'\n';
    fi(i, 1, n) cout << a[i] << " ";
    cout << '\n';
    fi(i, 1, n) cout << vt[num[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 (stderr)

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: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50