제출 #1282342

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282342		dex111222333444555	Railway (BOI17_railway)	C++20	100 / 100	63 ms	20272 KiB

railway

#include <bits/stdc++.h>
#define all(v) begin(v), end(v)
using namespace std;
const int MAXN = 1e5 + 5;

struct edge{
    int u, v;
    edge(int _u = 0, int _v = 0): u(_u), v(_v) {};
    int other(int x){
        return u ^ v ^ x;
    }
};

int numNode, numQuery, numReq, sta[MAXN], fin[MAXN], dp[MAXN], chain[MAXN], par[MAXN], sz[MAXN], cnt[MAXN], h[MAXN];
vector<int> adj[MAXN];
edge e[MAXN];

void dfsInit(int u){
    sz[u] = 1;
    for(int id: adj[u]) if (e[id].other(u) != par[u]) {
        int v = e[id].other(u); par[v] = u;
        dfsInit(v);
        sz[u] += sz[v];
    }
    sort(all(adj[u]), [&](const int &idA, const int &idB){
        int a = e[idA].other(u);
        int b = e[idB].other(u);
        return (a == par[u] ? INT_MIN: sz[a]) > (b == par[u] ? INT_MIN: sz[b]);
    });
}

void dfs(int u, bool isHeavy = 0){
    chain[u] = (isHeavy ? chain[par[u]]: u);
    sta[u] = ++sta[0];
    for(int id: adj[u]) if (e[id].other(u) != par[u]){
        int v = e[id].other(u); h[v] = h[u] + 1;
        dfs(v, id == adj[u][0]);
    }
    fin[u] = sta[0];
}

int lca(int u, int v){
    while(chain[u] != chain[v]){
        int up = par[chain[u]], vp = par[chain[v]];
        if (up == vp) u = up, v = vp;
        else if (h[up] < h[vp]) v = vp;
        else u = up;
    }
    return (h[u] < h[v] ? u: v);
}

void update(int u, int v){
    int p = lca(u, v);
    dp[u]++; dp[v]++; dp[p] -= 2;
}

void dfsGet(int u){
    for(int id: adj[u]) if (e[id].other(u) != par[u]){
        int v = e[id].other(u);
        dfsGet(v);
        dp[u] += dp[v];
        cnt[id] += dp[v];
    }
}

void input(){
    cin >> numNode >> numQuery >> numReq;
    int u, v;
    for(int i = 1; i < numNode; i++){
        cin >> u >> v;
        adj[u].push_back(i);
        adj[v].push_back(i);
        e[i] = {u, v};
    }
}

void solve(){
    h[0] = -1;
    dfsInit(1);
    dfs(1);
    while(numQuery--){
        int numCan; cin >> numCan;
        vector<int> can;
        for(int i = 1; i <= numCan; i++){
            int x; cin >> x;
            can.push_back(x);
        }
        sort(all(can), [&](const int &a, const int &b){
            return sta[a] < sta[b];
        });
        for(int i = 0; i < (int)can.size(); i++){
            update(can[i], can[(i + 1) % numCan]);
        }
    }
    dfsGet(1);
    vector<int> ans;
    for(int i = 1; i < numNode; i++) if (cnt[i] >= 2 * numReq){
        ans.push_back(i);
    }
    cout << (int)ans.size() << '\n';
    for(int x: ans) cout << x << ' '; cout << '\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen("test.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    input();
    solve();
}

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

railway.cpp: In function 'int main()':
railway.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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