Submission #255076

#	Time	Username	Problem	Language	Result	Execution time	Memory
255076		davitmarg	Village (BOI20_village)	C++17	0 / 100	5 ms	4992 KiB

Village

/*
DavitMarg
In a honky-tonk,
Down in Mexico
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0)
using namespace std;

const int N = 200005;

int n,used[N],vin[N],ans[N],sz[N],sum;
vector<int> g[N];

void dfs(int v,int p)
{
    vin[v] = v;
    sz[v] = g[v].size();
    for (int i = 0; i < g[v].size(); i++)
    {
        int to = g[v][i];
        if (to == p)
            continue;
        dfs(to, v);
        sz[v]--;
    }
    if (!used[v] || (v != p && sz[p]==1 && !used[p]))
    {
        swap(vin[v], vin[p]);
        ans[vin[p]] = p;
        ans[vin[v]] = v;
        used[v] = used[p] = 1;
        sum += 2;
    }
}

int main()
{
    fastIO;
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1, 1);
    cout << sum << endl;
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    cout << endl;

    return 0;
}

/*


*/

Compilation message (stderr)

Village.cpp: In function 'void dfs(int, int)':
Village.cpp:41:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++)
                     ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 38
• Subtask 3: 0 / 50