Submission #1096343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096343		ducdev	Railway (BOI17_railway)	C++14	52 / 100	205 ms	67368 KiB

railway

// Author: 4uckd3v - Nguyen Cao Duc
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int MAX_N = 3e5;
const int MOD = 1e9 + 7;

int n, m, k, lg, timer;
int up[MAX_N + 5][20], tin[MAX_N + 5], tout[MAX_N + 5];
vector<int> queries[MAX_N + 5];
vector<ii> adj[MAX_N + 5];

void dfs(int u, int p) {
    tin[u] = ++timer;
    up[u][0] = p;
    for (int i = 1; i <= lg; i++)
        up[u][i] = up[up[u][i - 1]][i - 1];

    for (ii e : adj[u]) {
        int v = e.first;
        if (v == p) continue;
        dfs(v, u);
    };

    tout[u] = ++timer;
};

bool isAncestor(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
};

int __lca(int u, int v) {
    if (isAncestor(u, v)) return u;
    if (isAncestor(v, u)) return v;

    for (int i = lg; i >= 0; i--)
        if (!isAncestor(up[u][i], v))
            u = up[u][i];

    return up[u][0];
};

namespace SUBTASK_1 {
    const int N = 1e4;

    bool mark[N + 5];
    int ans[N + 5];

    bool dfs(int u, int par) {
        bool ok = mark[u];
        for (ii e : adj[u]) {
            int v = e.first, id = e.second;
            if (v == par) continue;
            if (dfs(v, u)) ok = true, ans[id]++;
        };
        return ok;
    };

    void Solve() {
        for (int i = 0; i < m; i++) {
            int lca = -1;
            for (int u : queries[i]) {
                if (lca == -1)
                    lca = u;
                else
                    lca = __lca(lca, u);
                mark[u] = true;
            };
            dfs(lca, up[lca][0]);
            for (int u : queries[i]) mark[u] = false;
        };

        vector<int> edgesId;
        for (int i = 1; i < n; i++) {
            if (ans[i] >= k) edgesId.push_back(i);
        };

        cout << edgesId.size() << '\n';
        for (int id : edgesId) cout << id << ' ';
        cout << '\n';
    }
}  // namespace SUBTASK_1

namespace SUBTASK_2 {
    const int N = MAX_N;

    int dp[N + 5];
    vector<int> edgesId;

    bool checkSubtask() {
        for (int i = 0; i < m; i++) {
            if (queries[i].size() > 2) return false;
        };
        return true;
    };

    void dfs(int u, int par) {
        for (ii e : adj[u]) {
            int v = e.first, id = e.second;
            if (v == par) continue;
            dfs(v, u);
            dp[u] += dp[v];
            if (dp[v] >= k) edgesId.push_back(id);
        };
    }

    void Solve() {
        for (int i = 0; i < m; i++) {
            if (queries[i].size() < 2) continue;
            int u = queries[i][0], v = queries[i][1];
            dp[u]++, dp[v]++;
            dp[__lca(u, v)] -= 2;
        };

        dfs(1, 1);

        sort(edgesId.begin(), edgesId.end());

        cout << edgesId.size() << '\n';
        for (int id : edgesId) cout << id << ' ';
        cout << '\n';
    };
};  // namespace SUBTASK_2

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (fopen("MAIN.INP", "r")) {
        freopen("MAIN.INP", "r", stdin);
        freopen("MAIN.OUT", "w", stdout);
    };

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

    lg = ceil(log2(n));
    dfs(1, 1);

    for (int i = 0; i < m; i++) {
        int sz;
        cin >> sz;
        queries[i].resize(sz);
        for (int &u : queries[i]) cin >> u;
    };

    if (SUBTASK_2::checkSubtask())
        return SUBTASK_2::Solve(), 0;

    SUBTASK_1::Solve();
};

Compilation message (stderr)

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

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