Submission #700069

#	Time	Username	Problem	Language	Result	Execution time	Memory
700069		TS_2392	Railway (BOI17_railway)	C++14	100 / 100	93 ms	24900 KiB

railway

#include <bits/stdc++.h>

#define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define SPEED ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define epl emplace
#define eb emplace_back

#define EL cout << '\n'
#define dbg(x) cout << #x << " = " << (x) << ' '
#define dbgp(x) cout << #x << " = (" << (x.fi) << ", " << (x.se) << ") "

#define fi first
#define se second
#define mp make_pair

#define sqr(x) (x) * (x)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define lwb lower_bound
#define upb upper_bound
#define ctz __builtin_ctzll
#define pct __builtin_popcountll

using namespace std;

typedef long long ll;
typedef long double ldb;
typedef unsigned int uint;
typedef unsigned long long ull;

typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, int> pii;
typedef pair<ldb, ldb> pld;
typedef pair<double, double> pdd;

template<class T1, class T2> bool minimize(T1 &a, T2 &b){return a > b ? a = b, true : false;}
template<class T1, class T2> bool maximize(T1 &a, T2 &b){return a < b ? a = b, true : false;}
const int N = 1e5 + 3;
int n, m, k, node[N], cnt[N];
int Tin[N], Timer, jmp[N][18], dep[N];
bool mark[N];
vector<int> res;
vector<pii> adj[N];
void dfsLca(int u, int par){
    Tin[u] = ++Timer;
    for(int i = 0; i < adj[u].size(); ++i){
        int v = adj[u][i].fi;
        if(v == par) continue;
        jmp[v][0] = u; dep[v] = dep[u] + 1;
        for(int j = 1; j <= 17; ++j){
            if(!jmp[v][j - 1]) break;
            jmp[v][j] = jmp[jmp[v][j - 1]][j - 1];
        }
        dfsLca(v, u);
    }
}
bool cmp(const int &a, const int &b){
    return Tin[a] < Tin[b];
}
int Lca(int u, int v){
    if(dep[u] < dep[v]) swap(u, v);
    for(int i = 17; i >= 0; --i) if(dep[u] - (1 << i) >= dep[v]){
        u = jmp[u][i];
    }
    if(u == v) return u;
    for(int i = 17; i >= 0; --i) if(jmp[u][i] != jmp[v][i]){
        u = jmp[u][i]; v = jmp[v][i];
    }
    return jmp[u][0];
}
void dfs(int u, int pre_id){
    for(int i = 0; i < adj[u].size(); ++i){
        int v, id; tie(v, id) = adj[u][i];
        if(id == pre_id) continue;
        dfs(v, id); cnt[u] += cnt[v];
    }
    if(pre_id && cnt[u] / 2 >= k) res.eb(pre_id);
}
int main(){
    SPEED;
    cin >> n >> m >> k;
    for(int i = 1; i < n; ++i){
        int u, v; cin >> u >> v;
        adj[u].eb(v, i); adj[v].eb(u, i);
    }
    dfsLca(1, 0);
    while(m--){
        int sz; cin >> sz;
        for(int i = 1; i <= sz; ++i) cin >> node[i];
        sort(node + 1, node + 1 + sz, cmp);
        node[sz + 1] = node[1];
        for(int i = 1; i <= sz; ++i){
            int u = node[i], v = node[i + 1];
            int lca = Lca(u, v);
            ++cnt[u]; ++cnt[v]; cnt[lca] -= 2;
        }
    }
    dfs(1, 0); sort(all(res));
    cout << res.size() << '\n';
    for(int &x : res) cout << x << ' ';
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void dfsLca(int, int)':
railway.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i = 0; i < adj[u].size(); ++i){
      |                    ~~^~~~~~~~~~~~~~~
railway.cpp: In function 'void dfs(int, int)':
railway.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i = 0; i < adj[u].size(); ++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