제출 #1279678

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279678		baotoan655	Railway (BOI17_railway)	C++20	100 / 100	60 ms	24148 KiB

railway

#include <bits/stdc++.h>
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;

const int N = 1e5 + 5, LG = 17;
int bit[N];
void upd(int i, int val) {
    for(++i; i < N; i += i & -i) bit[i] += val;
}
int get(int i) {
    int res = 0;
    for(++i; i > 0; i -= i & -i) res += bit[i];
    return res;
}
int n, m, k;
vector<int> g[N];
int up[N][LG], idx[N], ps[N], dep[N], in[N], out[N], tim;
struct edge {
    int u, v;
    int other(int x) {
        return u ^ v ^ x;
    }
} ed[N];

void dfs(int u) {
    in[u] = ++tim;
    for(int id : g[u]) {
        int v = ed[id].other(u);
        if(v == up[u][0]) continue;
        up[v][0] = u;
        dep[v] = dep[u] + 1;
        idx[v] = id;
        for(int i = 1; i < LG; ++i) up[v][i] = up[up[v][i - 1]][i - 1];
        dfs(v);
    }
    out[u] = tim;
}
int lca(int u, int v) {
    if(dep[u] < dep[v]) swap(u, v);
    int d = dep[u] - dep[v];
    for(int i = LG - 1; i >= 0; --i) if(d >> i & 1) u = up[u][i];
    if(u == v) return u;
    for(int i = LG - 1; i >= 0; --i) {
        if(up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    file("A") else file("task");
    cin >> n >> m >> k;
    for(int i = 1; i < n; ++i) {
        cin >> ed[i].u >> ed[i].v;
        g[ed[i].u].emplace_back(i);
        g[ed[i].v].emplace_back(i);
    }
    dfs(1);
    for(int _ = 1; _ <= m; ++_) {
        int s;
        cin >> s;
        vector<int> ve(s);
        for(int &x : ve) cin >> x;
        sort(ve.begin(), ve.end(), [&](int x, int y) {
            return in[x] < in[y];
        });
        ve.emplace_back(ve[0]);
//        cout << s << '\n';
        for(int i = 0; i < (int)ve.size() - 1; ++i) {
            int u = ve[i], v = ve[i + 1];
            int p = lca(u, v);
//            cout << u << ' ' << v << ' ' << p << '\n';
            upd(in[u], 1);
            upd(in[v], 1);
            upd(in[p], -2);
        }
    }
    vector<int> ans;
    for(int i = 2; i <= n; ++i) {
        if(get(out[i]) - get(in[i] - 1) >= 2 * k) ans.emplace_back(idx[i]);
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for(int x : ans) cout << x << ' ';
    return 0;
}

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

railway.cpp: In function 'int main()':
railway.cpp:2:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:56:5: note: in expansion of macro 'file'
   56 |     file("A") else file("task");
      |     ^~~~
railway.cpp:2:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:56:5: note: in expansion of macro 'file'
   56 |     file("A") else file("task");
      |     ^~~~
railway.cpp:2:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:56:20: note: in expansion of macro 'file'
   56 |     file("A") else file("task");
      |                    ^~~~
railway.cpp:2:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:56:20: note: in expansion of macro 'file'
   56 |     file("A") else file("task");
      |                    ^~~~

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