Submission #128726

#	Time	Username	Problem	Language	Result	Execution time	Memory
128726		SamAnd	Railway (BOI17_railway)	C++17	100 / 100	315 ms	46660 KiB

railway

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;

int n, m, k;
vector<int> a[N];
vector<int> t[N];
vector<int> b[N];

int u[N];
int q[N];
map<int, int> mp[N];

vector<int> ans;
void dfs(int x, int p, int ki)
{
    for (int i = 0; i < b[x].size(); ++i)
    {
        int y = b[x][i];
        mp[x][y]++;
        if (mp[x][y] == u[y])
            ++q[x];
    }
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (h == p)
            continue;
        dfs(h, x, t[x][i]);
        if (mp[h].size() > mp[x].size())
        {
            swap(mp[h], mp[x]);
            swap(q[h], q[x]);
        }
        for (map<int, int>::iterator it = mp[h].begin(); it != mp[h].end(); ++it)
        {
            int y = it->first;
            int qq = it->second;
            mp[x][y] += qq;
            if (mp[x][y] == u[y])
                ++q[x];
        }
    }
    if (mp[x].size() - q[x] >= k)
        ans.push_back(ki);
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n - 1; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        a[x].push_back(y);
        a[y].push_back(x);
        t[x].push_back(i);
        t[y].push_back(i);
    }
    for (int i = 1; i <= m; ++i)
    {
        int s;
        scanf("%d", &s);
        u[i] = s;
        while (s--)
        {
            int x;
            scanf("%d", &x);
            b[x].push_back(i);
        }
    }
    dfs(1, 1, 0);
    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); ++i)
        cout << ans[i] << ' ';
    cout << endl;
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void dfs(int, int, int)':
railway.cpp:17:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < b[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
railway.cpp:24:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
railway.cpp:44:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (mp[x].size() - q[x] >= k)
         ~~~~~~~~~~~~~~~~~~~~^~~~
railway.cpp: In function 'int main()':
railway.cpp:75:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < ans.size(); ++i)
                     ~~^~~~~~~~~~~~
railway.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
railway.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~
railway.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &s);
         ~~~~~^~~~~~~~~~
railway.cpp:68:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~

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