Submission #960080

#	Time	Username	Problem	Language	Result	Execution time	Memory
960080		Flan312	Railway (BOI17_railway)	C++17	100 / 100	88 ms	24444 KiB

railway

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define eb emplace_back
#define task ""
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
#define fi first
#define se second
#define pii pair <int, int>
#define tii tuple <int, int, int>
using namespace std;
const int nmax = 1e5 + 2;
int n, m, k;
vector <pii> adj[nmax];
int in[nmax], out[nmax], up[nmax][17], indfs = 0;
int pos[nmax];
void dfs(int u)
{
    in[u] = ++indfs;
    for (auto &[v, i] : adj[u])
    {
        if (v == up[u][0]) continue;
        up[v][0] = u;
        pos[v] = i;
        for (int j = 1; (1 << j) <= n; ++j)
            up[v][j] = up[up[v][j - 1]][j - 1];
        dfs(v);
    }
    out[u] = indfs;
}
bool is_ancestor(int u, int v)
{
    return in[u] <= in[v] && in[v] <= out[u];
}
int lca(int u, int v)
{
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;
    for (int i = 16; i >= 0; --i)
    {
        int pu = up[u][i];
        if (pu > 0 && !is_ancestor(pu, v)) u = pu;
    }
    return up[u][0];
}
int dp[nmax];
bool can[nmax];
int dfs2(int u)
{
    for (auto &[v, i] : adj[u])
    {
        if (v == up[u][0]) continue;
        dp[u] += dfs2(v);
    }
    if (dp[u] >= 2*k) can[pos[u]] = 1;
    return dp[u];
}
int main()
{
    if (ifstream(task".inp")) nx
    fast
    cin >> n >> m >> k;
    for (int u, v, i = 1; i < n; ++i)
    {
        cin >> u >> v;
        adj[u].eb(v, i);
        adj[v].eb(u, i);
    }
    dfs(1);
    for (int i = 1; i <= m; ++i)
    {
        int s;
        cin >> s;
        vector <int> ver(s);
        for (auto &j : ver) cin >> j;
        sort(ver.begin(), ver.end(), [&](int i, int j)
        {
            return in[i] < in[j];
        });
        for (int i = 0; i < ver.size(); ++i)
        {
            ++dp[ver[i]];
            ++dp[ver[(i + 1) % s]];
            dp[lca(ver[i], ver[(i + 1) % s])] -= 2;
        }
    }
    dfs2(1);
    int ans = 0;
    for (int i = 1; i < n; ++i)
        if (can[i]) ++ans;
    cout << ans << '\n';
    for (int i = 1; i < n; ++i)
        if (can[i]) cout << i << ' ';
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:81:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for (int i = 0; i < ver.size(); ++i)
      |                         ~~^~~~~~~~~~~~
railway.cpp:7:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
railway.cpp:61:31: note: in expansion of macro 'nx'
   61 |     if (ifstream(task".inp")) nx
      |                               ^~
railway.cpp:7:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |                                            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:61:31: note: in expansion of macro 'nx'
   61 |     if (ifstream(task".inp")) nx
      |                               ^~

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