oj.uz

Submission #255076

# Submission time Handle Problem Language Result Execution time Memory
255076 2020-07-31T07:55:22 Z davitmarg Village (BOI20_village) C++17
0 / 100
 5 ms 4992 KB 
/*
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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 4992 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4992 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 4992 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -