Submission #390450

#	Time	Username	Problem	Language	Result	Execution time	Memory
390450		blue	Railway (BOI17_railway)	C++17	100 / 100	237 ms	22604 KiB

railway

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
For each deputy minister, a track is relevant if there is at least one neighborhood on either side.

If nodes are in DFS order, a deputy minister wants to build an edge if there is >=1 station inside its range and
 >=1 station outside its range.

Locate smallest and largest DFS labels in a DM's set.
Mo's algorithm over DFS subtree ranges
*/

const int maxn = 1e5;

vector<int> edge[1+maxn];
vector<int> edgelabel[1+maxn];
vector<int> querylabel(1+maxn, 0);

vector<int> label(1+maxn, 0);
int ct = 0;
vector<int> subtree(1+maxn, 1);

int rt = 0;

void dfs(int u)
{
    ct++;
    label[u] = ct;

    for(int i = 0; i < edge[u].size(); i++)
    {
        int v = edge[u][i];
        if(label[v]) continue;

        querylabel[v] = edgelabel[u][i];
        dfs(v);
        subtree[u] += subtree[v];
    }
}


int main()
{
    int n, m, k;
    cin >> n >> m >> k;

    for(int i = 1; i <= n-1; i++)
    {
        int a, b;
        cin >> a >> b;

        edge[a].push_back(b);
        edgelabel[a].push_back(i);

        edge[b].push_back(a);
        edgelabel[b].push_back(i);
    }

    while((rt+1)*(rt+1) <= n) rt++;

    dfs(1);

    vector<int> nodes(n);
    for(int i = 0; i < n; i++) nodes[i] = i+1;


    sort(nodes.begin(), nodes.end(),
        [] (int x, int y)
        {
            if(label[x] / rt == label[y] / rt)
                return label[x] + subtree[x] < label[y] + subtree[y];
            else return label[x] / rt < label[y] / rt;
        }
    );


    vector<int> ministers[n+1];
    vector<int> s(m+1, 0);

    for(int j = 1; j <= m; j++)
    {
        cin >> s[j];

        for(int x = 1; x <= s[j]; x++)
        {
            int q;
            cin >> q;
            ministers[ label[q] ].push_back(j);
        }
    }

    // for(int i = 1; i <= n; i++) cout << label[i] << ' ';
    // cout << '\n';
    //
    // for(int i = 1; i <= n; i++)
    // {
    //     cout << i << " -> ";
    //     for(int j: ministers[i]) cout << j << ' ';
    //
    //     cout << '\n';
    // }
    //
    // for(int g: nodes) cout << g << ' ' << label[g] << ' ' << label[g] + subtree[g] - 1 << '\n';
    // cout << '\n';

    // for(int i = 1; i <= n; i++) cout << querylabel[i] << ' ';
    // cout << '\n';

    vector<int> res;

    vector<int> curr_ct(m+1, 0); //count number of ministers inside the range
    int ct_active = 0;

    int l = 0, r = 0;
    for(int q: nodes)
    {
        while(l > label[q])
        {
            l--;
            for(int mini: ministers[l])
            {
                if(curr_ct[mini] == 0)
                    ct_active++;

                curr_ct[mini]++;

                if(curr_ct[mini] == s[mini])
                    ct_active--;
            }
        }

        while(r < label[q] + subtree[q] - 1)
        {
            r++;
            for(int mini: ministers[r])
            {
                if(curr_ct[mini] == 0)
                    ct_active++;

                curr_ct[mini]++;

                if(curr_ct[mini] == s[mini])
                    ct_active--;
            }
        }

        while(l < label[q])
        {
            for(int mini: ministers[l])
            {
                if(curr_ct[mini] == s[mini])
                    ct_active++;

                curr_ct[mini]--;

                if(curr_ct[mini] == 0)
                    ct_active--;
            }
            l++;
        }

        while(r > label[q] + subtree[q] - 1)
        {
            for(int mini: ministers[r])
            {
                if(curr_ct[mini] == s[mini])
                    ct_active++;

                curr_ct[mini]--;

                if(curr_ct[mini] == 0)
                    ct_active--;
            }
            r--;
        }

        // cout << l << ' ' << r << ": ";
        // for(int i = 1; i <= m; i++) cout << curr_ct[i] << ' ';
        // cout << '\n';
        // cout << ct_active << '\n';


        if(ct_active >= k)
            res.push_back(querylabel[q]);
    }

    sort(res.begin(), res.end());
    cout << res.size() << '\n';
    for(int R: res) cout << R << ' ';
    cout << '\n';
}

Compilation message (stderr)

railway.cpp: In function 'void dfs(int)':
railway.cpp:33:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i = 0; i < edge[u].size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~

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