Submission #540560

#	Time	Username	Problem	Language	Result	Execution time	Memory
540560		Evang	Railway (BOI17_railway)	C++17	100 / 100	102 ms	25572 KiB

railway

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

#ifdef _DEBUG
#define dout(x) clog << "Line " << __LINE__ << ": " << #x << "=" << (x) << el
#else
#define dout(x)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define uid(a,b) uniform_int_distribution<int>(a,b)(rng)

#define ins insert
#define ssize(x) (int((x).size()))
#define bs(args...) binary_search(args)
#define lb(args...) lower_bound(args)
#define ub(args...) upper_bound(args)
#define all(x) (x).begin(),(x).end()
#define mp(a, b) make_pair(a, b)
#define mt(args...) make_tuple(args)
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define die exit(0)

template<typename T>
using vc = vector<T>;
template<typename T>
using uset = unordered_set<T>;
template<typename A, typename B>
using umap = unordered_map<A, B>;
template<typename T, typename Comp>
using pq = std::priority_queue<T, vc<T>, Comp>;
template<typename T>
using maxpq = pq<T, less<T>>;
template<typename T>
using minpq = pq<T, greater<T>>;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using db = double;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vc<int>;
using vll = vc<ll>;
using vpi = vc<pi>;
using vpll = vc<pll>;
using str = string;

constexpr char el = '\n';
constexpr char sp = ' ';
constexpr int inf = 0x3f3f3f3f;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3fLL;
// ---------------------------------------------------------------------


const int N = 1e5+5;
const int LG = 20;
// pa[i] = the ID of the edge connecting node i with i's parent
// cnt[i] = edge's i's value; how many Ministers need edge i
int n, m, k, pa[N], cnt[N], a[N], tin[N], tout[N], up[N][LG];
struct edge {
    edge(int x, int y): u(x), id(y) {}
    int u, id;
};
vc<edge> adj[N];

struct BIT {
    int bit[2*N];
    void _upd(int i, int x){
        while(i<=n){
            bit[i] += x;
            i += i&-i;
        }
    }
    int _qry(int r){
        int ans = 0;
        while(r>0){
            ans += bit[r];
            r -= r&-r;
        }
        return ans;
    }
    int _qry(int l, int r){
        return _qry(r) - _qry(l - 1);
    }
    void upd(int l, int r, int x){
        _upd(l, x);
        _upd(r+1, -x);
    }
    int qry(int i){
        return _qry(1, i);
    }
} bit;

void dfs(int v, int p){
    static int tim = 0;
    tin[v] = ++tim;
    up[v][0] = p;
    for(int i = 1; i < LG; ++i)
        up[v][i] = up[up[v][i-1]][i-1];

    for(auto[u, id]: adj[v])
        if(u!=p) {
            pa[u] = id;
            dfs(u, v);
        }
    tout[v] = tim;
}

bool is_anc(int x, int y){
    // is x y's ancestor?
    return tin[x] <= tin[y] && tout[y] <= tout[x];
}

int lca(int x, int y){
    if(is_anc(x, y))
        return x;

    for(int i = LG-1; i >= 0; --i)
        if(up[x][i]&&!is_anc(up[x][i], y))
            x = up[x][i];

    return up[x][0];
}

void upd(int x, int y){
    // increment all edges of the path from x to y
    // to increment an edge (v, u), where v is the parent,
    // increment a[u]
    if(is_anc(x, y)){
        cnt[pa[x]]--;
        cnt[pa[y]]++;
        return;
    }
    if(is_anc(y, x)){
        cnt[pa[y]]--;
        cnt[pa[x]]++;
        return;
    }

    int an = lca(x, y);
    cnt[pa[x]]++;
    cnt[pa[y]]++;
    cnt[pa[an]] -= 2;
}

void dfs2(int v, int p){
    for(auto[u, _]: adj[v]){
        if(u!=p) {
            dfs2(u, v);
            cnt[pa[v]] += cnt[pa[u]];
        }
    }
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout << fixed; clog << fixed; clog << unitbuf;
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#else
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
#endif

    cin >> n >> m >> k;
    for(int i = 1; i < n; ++i){
        int x, y;
        cin >> x >> y;
        adj[x].eb(y, i);
        adj[y].eb(x, i);
    }
    dfs(1, 0);

    while(m--){
        int s;
        cin >> s;
        vi b;
        for(int i = 0; i < s; ++i){
            int x;
            cin >> x;
            b.pb(x);
        }
        sort(all(b), [](int x, int y){
            return tin[x] < tin[y];
        });
        b.pb(b[0]);

        for(int i = 0; i < s; ++i)
            upd(b[i], b[i+1]);
    }

    dfs2(1, 0);

    int ans = 0;
    for(int i = 1; i < n; ++i)
        if(cnt[i]>=2*k)
            ++ans;

    cout << ans << el;
    for(int i = 1; i < n; ++i)
        if(cnt[i]>=2*k)
            cout << i << sp;

#ifdef _DEBUG
    clog << "Line " << __LINE__ << ":\n";
    for(int i = 1; i <= n; ++i)
        clog << pa[i] << sp;
    clog << el;
#endif

#ifdef _DEBUG
    clog << "Line " << __LINE__ << ":\n";
    for(int i = 1; i < n; ++i)
        clog << cnt[i] << sp;
    clog << el;
#endif
}

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