제출 #1096330

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1096330		tachvoi	Railway (BOI17_railway)	C++14	0 / 100	4 ms	5212 KiB

railway

#include <bits/stdc++.h>  

using namespace std;
#define N 200005
#define LOG 17

int tin[N], depth[N], timer, par[N][LOG], dp[N], n, q, k;
vector <int> adj[N], ans;
map <pair <int, int>, int> lab;

void dfs1(int u)
{
    tin[u] = ++timer;
    for (int v : adj[u])
        if (v != par[u][0]) par[v][0] = u, depth[v] = depth[u] + 1, dfs1(v);
}

int getlca(int u, int v)
{
    if (depth[u] < depth[v]) swap(u, v);

    for (int k = LOG - 1; k >= 0; k--)
        if (par[u][k] && depth[par[u][k]] >= depth[v]) u = par[u][k];

    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; k--)
        if (par[u][k] != par[v][k])
        {
            u = par[u][k];
            v = par[v][k];
        }

    return par[u][0];
}

void dfs2(int u)
{
    for (int v : adj[u])
        if (v != par[u][0]) dfs2(v), dp[u] += dp[v];

    if (dp[u] >= 2 * k) ans.push_back(lab[{u, par[u][0]}]);
}

bool cmp(int &x, int &y)
{
    return tin[x] < tin[y];
}

signed main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    
    #ifndef ONLINE_JUDGE
    freopen("input.inp","r",stdin);
    freopen("output.out","w",stdout);
    #endif 

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

    dfs1(1);
    for (int k = 1; k < LOG; k++)
        for (int u = 1; u <= n; u++)
            par[u][k] = par[par[u][k - 1]][k - 1];

    while (q--)
    {
        int m; cin >> m; vector <int> vec;
        for (int i = 1; i <= m; i++)
        {
            int x; cin >> x;
            vec.push_back(x);
        }

        sort(vec.begin(), vec.end()); vec.push_back(vec[0]);
        for (int i = 1; i < vec.size(); i++)
        {
            int u = vec[i - 1], v = vec[i];
            int lca = getlca(u, v);
            dp[u]++; dp[v]++; dp[lca] -= 2;
        }
    }

    dfs2(1); sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for (int x : ans) cout << x << ' ';
}

컴파일 시 표준 에러 (stderr) 메시지

railway.cpp: In function 'int main()':
railway.cpp:83:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for (int i = 1; i < vec.size(); i++)
      |                         ~~^~~~~~~~~~~~
railway.cpp:55:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     freopen("input.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:56:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     freopen("output.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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