Submission #951141

#	Time	Username	Problem	Language	Result	Execution time	Memory
951141		inkvizytor	Railway (BOI17_railway)	C++14	100 / 100	173 ms	38352 KiB

railway

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

int k;

int logarytm(int a) {
    int w = 0;
    while (a > 0) {
        w++;
        a /= 2;
    }
    return w+1;
}

int l;
vector<vector<pair<int, int>>> g;
vector<int> o;
vector<int> d;
vector<bool> odw;
vector<vector<int>> p;
vector<vector<int>> w;
vector<vector<int>> sp;
vector<vector<int>> jp;

void dfs (int v) {
    odw[v] = 1;
    for (int x : w[v]) {
        sp[x].push_back(v);
    }
    for (auto u : g[v]) {
        if (!odw[u.fi]) {
            o[u.fi] = v;
            d[u.fi] = d[v]+1;
            dfs(u.fi);
        }
    }
}

int lca (int a, int b) {
    int w;
    w = l-1;
    while (d[a] > d[b]) {
        if (d[jp[a][w]] >= d[b]) {
            a = jp[a][w];
        }
        w--;
    }
    w = l-1;
    while (d[b] > d[a]) {
        if (d[jp[b][w]] >= d[a]) {
            b = jp[b][w];
        }
        w--;
    }
    w = l-1;
    while (w >= 0) {
        if (jp[a][w] != jp[b][w]) {
            a = jp[a][w];
            b = jp[b][w];
        }
        w--;
    }
    if (a != b) {
        return o[a];
    }
    return a;
}

vector<bool> odw2;
vector<int> z;
vector<int> kr;

void dfs2 (int v, int ko) {
    odw2[v] = 1;
    for (auto u : g[v]) {
        if (!odw2[u.first]) {
            dfs2(u.first, u.second);
            z[v] += z[u.first];
        }
    }
    if (z[v] >= 2*k) {
        kr.push_back(ko);
    }
}

int main() {
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);
    int n, m;
    cin >> n >> m >> k;
    g.resize(n+1);
    vector<pair<int, int>> s (n, make_pair(0, 0));
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(make_pair(b, i));
        g[b].push_back(make_pair(a, i));
        s[i] = make_pair(a, b);
    }
    p.resize(m);
    w.resize(n+1);
    sp.resize(m);
    for (int i = 0; i < m; i++) {
        int s;
        cin >> s;
        p[i].resize(s);
        for (int j = 0; j < s; j++) {
            cin >> p[i][j];
            w[p[i][j]].push_back(i);
        }
    }
    o.resize(n+1, 0);
    d.resize(n+1, 0);
    odw.resize(n+1, 0);
    o[1] = 1;
    d[1] = 0;
    dfs(1);
    l = logarytm(n);
    jp.resize(n+1, vector<int>(l, 0));
    for (int i = 1; i < n+1; i++) {
        jp[i][0] = o[i];
    }
    for (int i = 1; i < l; i++) {
        for (int j = 1; j < n+1; j++) {
            jp[j][i] = jp[jp[j][i-1]][i-1];
        }
    }
    z.resize(n+1, 0);
    for (auto x : sp) {
        for (int i = 0; i < x.size()-1; i++) {
            z[x[i]]++;
            z[x[i+1]]++;
            z[lca(x[i], x[i+1])] -= 2;
        }
        z[x[0]]++;
        z[x[x.size()-1]]++;
        z[lca(x[0], x[x.size()-1])] -= 2;
    }
    odw2.resize(n+1, 0);
    dfs2(1, 0);
    cout << kr.size() << '\n';
    sort(kr.begin(), kr.end());
    for (int x : kr) {
        cout << x << ' ';
    }
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:132:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |         for (int i = 0; i < x.size()-1; i++) {
      |                         ~~^~~~~~~~~~~~

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