Submission #1109090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109090		lmToT27	Railway (BOI17_railway)	C++17	100 / 100	66 ms	24136 KiB

railway

#include <bits/stdc++.h>
#define all(dataStructure) dataStructure.begin(),dataStructure.end()

typedef long long ll;

using namespace std;
namespace std {
        template <typename T, int D>
        struct _vector : public vector <_vector <T, D - 1>> {
                static_assert(D >= 1, "Dimension must be positive!");
                template <typename... Args>
                _vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
        };
        // _vector <int, 3> a(n, m, k);: int a[n][m][k].
        // _vector <int, 3> a(n, m, k, x);: int a[n][m][k] initialized with x.
        template <typename T>
        struct _vector <T, 1> : public vector <T> {
                _vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
        };
}

const int MAX = 1e5 + 3;
const ll MOD[] = {1000000007, 998244353};

int n, m, k;
vector <int> adj[MAX];
int u[MAX], v[MAX];
int cnt[MAX];
int depth[MAX], tin[MAX], tout[MAX], timeDfs;
int pa[MAX][18];

void dfs(int u, int pre) {
        depth[u] = depth[pre] + 1;
        tin[u] = ++timeDfs;
        pa[u][0] = pre;
        for (int i = 1; i <= 17; i++) pa[u][i] = pa[pa[u][i - 1]][i - 1];
        for (int &v : adj[u]) if (v != pre) dfs(v, u);
        tout[u] = timeDfs;
}

int __lca(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        int dist = depth[u] - depth[v];

        while (dist) {
                u = pa[u][__builtin_ctz(dist)];
                dist -= dist & -dist;
        }
        
        if (u == v) {
                return u;
        } else {
                for (int i = 17; i >= 0; i--) {
                        if (pa[u][i] != pa[v][i]) {
                                u = pa[u][i];
                                v = pa[v][i];
                        }
                }
                return pa[u][0];
        }
}

void reDfs(int u, int pre) {
        for (int &v : adj[u]) if (v != pre) {
                reDfs(v, u);
                cnt[u] += cnt[v];
        }
}

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

        dfs(1, 0);

        while (m--) {
                int sz;
                cin >> sz;
                vector <int> V(sz);
                for (int &x : V) cin >> x;
                sort(all(V), [&](const int &i, const int &j) {
                        return tin[i] < tin[j];
                });
                for (int i = 0; i < sz; i++) {
                        cnt[V[i]]++;
                        cnt[__lca(V[i], V[(i + 1) % sz])]--;
                }
        }

        reDfs(1, 0);

        int cntAns = 0;

        for (int i = 1; i < n; i++) {
                if (depth[u[i]] < depth[v[i]]) swap(u[i], v[i]);
                if (cnt[u[i]] >= k) cntAns++;
        }

        cout << cntAns << '\n';

        for (int i = 1; i < n; i++) {
                if (cnt[u[i]] >= k) cout << i << ' ';
        }
}

int32_t main() {
        std::ios_base::sync_with_stdio(0);
        std::cin.tie(0); std::cout.tie(0);

        #define TASK "TR"
        if (fopen(TASK".INP", "r")) {
                freopen(TASK".INP", "r", stdin);
                freopen(TASK".OUT", "w", stdout);
        }
        
        if (fopen("TASK.INP", "r")) {
                freopen("TASK.INP", "r", stdin);
                freopen("TASK.OUT", "w", stdout);
        }
        
        /* int TEST = 1; cin >> TEST; while (TEST--) */ Solve();

        cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
        return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int32_t main()':
railway.cpp:116:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |                 freopen(TASK".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:117:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |                 freopen(TASK".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:121:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |                 freopen("TASK.INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:122:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |                 freopen("TASK.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