Submission #253779

#	Time	Username	Problem	Language	Result	Execution time	Memory
253779		test2	Railway (BOI17_railway)	C++14	100 / 100	494 ms	57068 KiB

railway

#include <bits/stdc++.h>

using namespace std;

const int N = (1 << 18);

int n, m, k;
int st[N], en[N];
vector<int> deps[N], ans;
int t = 3, r, r2;
int L[N], R[N];
vector<pair<int, int>> adj[N];
int er[N];
vector<pair<pair<int, int>, int>> eve, eve2;

int an1[N], an2[N];
int bit[N][2];

void add(int x, int idx = 0, int val = 1)
{
        for (; x < N; x += x & -x)
                bit[x][idx] += val;
}
int get(int x, int idx = 0, int val = 1)
{
        int ret = 0;
        for (; x; x -= x & -x)
                ret += bit[x][idx];
        return ret;
}

void solve1()
{
        sort(eve.begin(), eve.end(), [&](pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
                if (a.first.first == b.first.first)
                {
                        return a.second < b.second;
                }
                return a.first < b.first;
        });
        vector<int> ends;
        map<int, int> qu;
        map<int, int> frs;
        for (auto u : eve)
        {
                if (u.second == 0)
                        qu[u.first.second] = u.first.first;

                else if (u.second == 1)

                        frs[u.first.second] = u.first.first;

                else if (u.second == 2)
                {
                        ends.push_back(frs[u.first.second]);
                        add((frs[u.first.second]));
                }
                else

                        an1[u.first.second] = get(N - 1) - get(qu[u.first.second] - 1);
        }
}

void solve2()
{
        memset(bit, 0, sizeof bit);
        sort(eve2.begin(), eve2.end(), [&](pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
                if (a.first.first == b.first.first)
                {
                        return a.second < b.second;
                }
                return a.first < b.first;
        });
        vector<int> ends;
        map<int, int> qu;
        map<int, int> frs;
        for (auto u : eve2)
        {

                if (u.second == 1)
                        qu[u.first.second] = u.first.first;

                else if (u.second == 0)
                {
                        frs[u.first.second] = u.first.first;
                        add(u.first.first, 1, 1);
                }
                else if (u.second == 3)
                {
                        ends.push_back(frs[u.first.second]);
                        add(frs[u.first.second], 1, -1);
                }
                else
                {
                        an2[u.first.second] = get(qu[u.first.second], 1);
                }
        }
}

void dfz(int x, int p)
{
        st[x] = ++t;
        for (auto u : adj[x])
        {
                if (u.first == p)
                        continue;
                dfz(u.first, x);
        }
        en[x] = ++t;
        return;
}

void dfs0(int x, int p)
{

        for (auto u : adj[x])
        {
                if (u.first == p)
                        continue;
                int cnt = m;
                er[u.second] = u.first;
                eve.push_back({{st[u.first], u.second}, 0});
                eve.push_back({{en[u.first], u.second}, 3});
                eve2.push_back({{st[u.first], u.second}, 1});
                eve2.push_back({{en[u.first], u.second}, 2});
                dfs0(u.first, x);
        }
        return;
}

void dfs(int x, int p)
{

        for (auto u : adj[x])
        {
                if (u.first == p)
                        continue;
                int cnt = m;

                cnt -= an1[u.second];
                cnt -= an2[u.second];

                if (cnt >= k)
                {
                        ans.push_back(u.second + 1);
                }
                dfs(u.first, x);
        }
        return;
}

int main()
{

        ios_base::sync_with_stdio(0);
        cin.tie(0);
        //freopen("in.in", "r", stdin);

        cin >> n >> m >> k;

        for (int i = 0; i < n - 1; i++)
        {
                int u, v;
                cin >> u >> v;
                adj[u].push_back({v, i});
                adj[v].push_back({u, i});
        }

        dfz(1, 1);

        for (int i = 0; i < m; i++)
        {
                int x;
                cin >> x;
                vector<int> vec;
                for (int j = 0; j < x; j++)
                {
                        int t;
                        cin >> t;
                        deps[i].push_back(t);
                        vec.push_back(st[t]);
                }
                sort(vec.begin(), vec.end());
                int l = 1;

                for (auto u : vec)
                {
                        if (u > l && l + 1 <= u - 1)
                        {
                                eve2.push_back({{l + 1, r2}, 0});
                                eve2.push_back({{u - 1, r2}, 3});
                                r2++;
                        }
                        l = u;
                }
                L[i] = vec[0];
                R[i] = vec.back();

                eve.push_back({{L[i], r}, 1});
                eve.push_back({{R[i], r}, 2});

                eve2.push_back({{l + 1, r2}, 0});
                eve2.push_back({{N - 1, r2}, 3});
                r2++;
                r++;
        }

        dfs0(1, 1);
        solve1();
        solve2();

        dfs(1, 1);

        cout << (int)ans.size() << "\n";
        sort(ans.begin(), ans.end());
        for (auto u : ans)
        {
                cout << u << " ";
        }

        return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void dfs0(int, int)':
railway.cpp:120:21: warning: unused variable 'cnt' [-Wunused-variable]
                 int cnt = m;
                     ^~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25