제출 #1264265

#제출 시각아이디문제언어결과실행 시간메모리
1264265MinhKienRailway (BOI17_railway)C++20
100 / 100
111 ms27372 KiB
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define ii pair <int, int>
#define fi first
#define se second

const int N = 2e5 + 10;

int n, m, k, x, y;
int par[N], dp[N];
int num, a[N], tim, in[N], out[N];
int depth[N], up[N][20], Log2[N];
vector <ii> v[N];
vector <int> ans;
bool ck[N];

void DFS(int s = 1, int p = -1) {
    in[s] = out[s] = ++tim;

    for (ii z: v[s]) {
        if (z.se == p) continue;

        par[z.se] = s;
        depth[z.se] = depth[s] + 1;

        up[z.se][0] = s;
        for (int i = 1; i <= Log2[depth[z.se]]; ++i) {
            up[z.se][i] = up[up[z.se][i - 1]][i - 1];
        }

        DFS(z.se, s);
        out[s] = out[z.se];
    }
}

int LCA(int A, int B) {
    if (depth[A] < depth[B]) swap(A, B);

    int step = depth[A] - depth[B];

    for (int i = 0; i <= Log2[step]; ++i) {
        if (step >> i & 1) A = up[A][i];
    }

    if (A == B) return A;

    for (int i = Log2[depth[A]]; i >= 0; --i) {
        if (up[A][i] != up[B][i]) {
            A = up[A][i];
            B = up[B][i];
        }
    }

    return up[A][0];
}

void Path(int A, int B) {
    ++dp[A]; ++dp[B];
    dp[LCA(A, B)] -= 2;
}

bool cmp(const int &A, const int &B) {
    return in[A] < in[B];
}

void dodp(int s = 1, int la = -1) {
    for (ii z: v[s]) {
        if (z.fi == la) continue;
        dodp(z.se, z.fi);
        dp[s] += dp[z.se];
    }

    if (dp[s] >= k) {
        ans.push_back(la);
    }
}

int main() {
    if (fopen("inp.txt", "r")) {
        freopen("inp.txt", "r", stdin);
    }

    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> n >> m >> k;
    for (int i = 1; i < n; ++i) {
        cin >> x >> y;
        v[x].push_back(ii(i, y));
        v[y].push_back(ii(i, x));

        if (i >= 2) Log2[i] = Log2[i >> 1] + 1;
    }

    DFS();

    while (m--) {
        cin >> num;
        for (int i = 1; i <= num; ++i) cin >> a[i];
        sort(a + 1, a + num + 1, cmp);

        Path(a[1], a[num]);
        for (int i = 1; i < num; ++i) {
            Path(a[i], a[i + 1]);
        }
    }

    k <<= 1;
    dodp();

    sort(ans.begin(), ans.end());
    cout << ans.size() << "\n";
    for (int z: ans) cout << z << " ";

    return 0;
}

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

railway.cpp: In function 'int main()':
railway.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen("inp.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...