Submission #390920

#	Time	Username	Problem	Language	Result	Execution time	Memory
390920		Victor	Railway (BOI17_railway)	C++17	0 / 100	59 ms	14912 KiB

railway

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = b - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;

const int INF = 1000000007;

vi ans;
int n, m, k, cnt[100001], layer[100001], curr, indx[100001], add[100001];
vii graph[100001];

bool dfs(int u, int p) {
    bool ret = (layer[u] == curr);
    trav(edge, graph[u]) if (edge.first != p) {
        if (dfs(edge.first, u)) ++cnt[edge.second], ret = 1;
    }
    return ret;
}

void line1(int u, int p, int depth) {
    indx[u] = depth;
    trav(edge, graph[u]) if (edge.first != p) {
        line1(edge.first, u, depth + 1);
    }
}


void line2(int u, int p, int val, int t) {
    if (k <= val) ans.pb(t);
    val += add[indx[u]];
    trav(v, graph[u]) if (v.first != p) {
        line2(v.first, u, val, v.second);
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    memset(cnt, 0, sizeof(cnt));
    memset(add, 0, sizeof(add));
    memset(layer, -1, sizeof(layer));
    cin >> n >> m >> k;

    int a, b;
    bool isline = 1;
    rep(i, 0, n - 1) {
        cin >> a >> b;
        graph[--a].emplace_back(--b, i);
        graph[b].emplace_back(a, i);
        if (2 < ++cnt[a] || 2 < ++cnt[b]) isline = 0;
    }

    if (isline) {
        int start;
        rep(i, 0, n) if (cnt[i] == 1) {
            start = i;
            break;
        }

        line1(start, start, 0);

        memset(cnt, 0, sizeof(cnt));
        rep(i, 0, m) {
            int s, u, mn = n, mx = 0;
            curr = i;
            cin >> s;
            rep(j, 0, s) {
                cin >> u;
                mn = min(mn, indx[--u]);
                mx = max(mx, indx[u]);
            }
            ++add[mn];
            --add[mx];
        }

        line2(start,start,0,0);
        sort(all(ans));
    }

    else if (n <= 10000 && m <= 2000) {
        memset(cnt, 0, sizeof(cnt));
        rep(i, 0, m) {
            int s, u;
            curr = i;
            cin >> s;
            rep(j, 0, s) cin >> u, layer[u - 1] = i;
            dfs(u - 1, u - 1);
        }
        rep(i, 0, n) {
            if (k <= cnt[i]) ans.pb(i + 1);
        }
    }

    cout << sz(ans) << endl;
    trav(edge, ans) cout << edge << ' ';
    cout << endl;
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:94:14: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
   94 |         line2(start,start,0,0);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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