Submission #381602

#	Time	Username	Problem	Language	Result	Execution time	Memory
381602		Vimmer	Pastiri (COI20_pastiri)	C++14	0 / 100	1114 ms	524292 KiB

pastiri

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("-O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-Ofast")

#define N 500050
#define NN 1005000
#define PB push_back
#define endl '\n'
#define pri(x) cout << x << endl
#define _ << " " <<
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define M ll(1e9 + 7)
#define F first
#define S second

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef short int si;
typedef unsigned long long ull;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

//ordered_set se;

int n, k;

bool mk[N], mkr[N];

set <int> g[N];

vector <pair <int, int> > who[N];

int main()
{
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

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

    cin >> n >> k;

    for (int i = 1; i < n; i++)
    {
        int x, y;

        cin >> x >> y;

        g[x].insert(y);

        g[y].insert(x);
    }

    for (int i = 0; i < k; i++)
    {
        int x;

        cin >> x;

        mk[x] = 1;
    }

    queue <int> qr;

    for (int i = 1; i <= n; i++)
    {
        if (mk[i])
        {
            mkr[i] = 1;

            who[i].PB({i, 0});
        }

        if (sz(g[i]) == 1)
        {
            qr.push(i);
        }
    }

    while (sz(qr))
    {
        int v = qr.front();

        qr.pop();

        int u = *g[v].begin();

        g[v].clear();

        g[u].erase(v);

        vector <pair <int, int> > cur; cur.clear();

        int i = 0, j = 0;

        while (i < sz(who[u]) || j < sz(who[v]))
        {
            pair <int, int> pt;

            if (j < sz(who[v]) && (i == sz(who[u]) || who[u][i].S > who[u][j].S))
            {
                pt = who[v][j++];

                pt.S++;
            }
            else
                pt = who[u][i++];

            if (sz(cur) == 1 && cur.back().S == pt.S)
                {
                    mkr[pt.F] = 0;

                    mkr[cur.back().F] = 0;

                    mkr[u] = 1;

                    cur.back().F = u;

                    continue;
                }
                else
                    cur.PB(pt);
        }

        if (sz(g[u]) == 1)
            qr.push(u);

        who[u] = cur;
    }

    vector <int> ans; ans.clear();

    for (int i = 1; i <= n; i++)
        if (mkr[i])
            ans.PB(i);

    pri(sz(ans));

    for (auto it : ans)
        cout << it << " ";
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 18
• Subtask 3: 0 / 23
• Subtask 4: 0 / 51