Submission #1125238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125238		dpsaveslives	Railway (BOI17_railway)	C++20	36 / 100	200 ms	30188 KiB

railway

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double; // or double if tight TL
using str = string;
using pi = pair<int,int>;
#define mp make_pair
#define f first
#define s second
#define tcT template<class T
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
using vi = V<int>;
using vb = V<bool>;
using vpi = V<pi>;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))
#define rsz resize
#define pb push_back
#define ft front()
#define bk back()
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)
const int MOD = 1e9+7;
const int SZ = (1<<18);
tcT> bool ckmin(T& a, const T& b) {
	return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
	return a < b ? a = b, 1 : 0; } // set a = max(a,b)
tcT, int SZ> struct LazySeg{
	const T ID{}; T cmb(T a, T b) { return a+b; }
	T seg[2*SZ], lazy[2*SZ];
	LazySeg() { F0R(i,2*SZ) seg[i] = lazy[i] = ID; }
	void push(int ind, int L, int R) {
		seg[ind] += (R-L+1)*lazy[ind];
		if (L != R) F0R(i,2) lazy[2*ind+i] += lazy[ind];
		lazy[ind] = 0;
	}
	void pull(int ind){seg[ind]=cmb(seg[2*ind],seg[2*ind+1]);}
	void build() { ROF(i,1,SZ) pull(i); }
	void upd(int lo,int hi,T inc,int ind=1,int L=0, int R=SZ-1) {
		push(ind,L,R); if (hi < L || R < lo) return;
		if (lo <= L && R <= hi) {
			lazy[ind] = inc; push(ind,L,R); return; }
		int M = (L+R)/2; upd(lo,hi,inc,2*ind,L,M);
		upd(lo,hi,inc,2*ind+1,M+1,R); pull(ind);
	}
	T query(int lo, int hi, int ind=1, int L=0, int R=SZ-1) {
		push(ind,L,R); if (lo > R || L > hi) return ID;
		if (lo <= L && R <= hi) return seg[ind];
		int M = (L+R)/2; return cmb(query(lo,hi,2*ind,L,M),
			query(lo,hi,2*ind+1,M+1,R));
	}
};
struct HLD{
	int N; vector<int> adj[SZ];
	int par[SZ], root[SZ], depth[SZ], sz[SZ], ti;
	int pos[SZ]; vector<int> rpos;
	void ae(int x, int y) { adj[x].pb(y), adj[y].pb(x); }
	void dfsSz(int x) {
		sz[x] = 1;
		each(y,adj[x]) {
			par[y] = x; depth[y] = depth[x]+1;
			adj[y].erase(find(all(adj[y]),x));
			dfsSz(y); sz[x] += sz[y];
			if (sz[y] > sz[adj[x][0]]) swap(y,adj[x][0]);
		}
	}
	void dfsHld(int x) {
		pos[x] = ti++; rpos.pb(x);
		each(y,adj[x]) {
			root[y] = (y == adj[x][0] ? root[x] : y);
			dfsHld(y); }
	}
	void init(int _N, int R = 0) { N = _N;
		par[R] = depth[R] = ti = 0; dfsSz(R);
		root[R] = R; dfsHld(R);
	}
	int lca(int x, int y) {
		for (; root[x] != root[y]; y = par[root[y]])
			if (depth[root[x]] > depth[root[y]]) swap(x,y);
		return depth[x] < depth[y] ? x : y;
	}
	LazySeg<ll,SZ> tree; //segtree for sum
	template <class BinaryOp>
	void processPath(int x, int y, BinaryOp op) {
		for (; root[x] != root[y]; y = par[root[y]]) {
			if (depth[root[x]] > depth[root[y]]) swap(x,y);
			op(pos[root[y]],pos[y]); }
		if (depth[x] > depth[y]) swap(x,y);
		op(pos[x]+1,pos[y]);
	}
	void modifyPath(int x, int y, int v) {
		processPath(x,y,[this,&v](int l, int r){ tree.upd(l,r,v); });
    }
	ll queryPath(int x, int y) {
		ll res = 0; processPath(x,y,[this,&res](int l, int r) {
			res += tree.query(l,r); });
		return res;
    }
	void modifySubtree(int x, int v){
		tree.upd(pos[x],pos[x]+sz[x]-1,v); }
}hld;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N,M,K; cin >> N >> M >> K;
    vector<pair<int,int>> edges;
    for(int i = 1;i<=N-1;++i){
        int a,b; cin >> a >> b;
        hld.adj[a].push_back(b); hld.adj[b].push_back(a);
        edges.push_back({a,b});
    }
    hld.init(N+1,1);
    for(int i = 1;i<=M;++i){
        int x; cin >> x;
        int last; cin >> last;
        for(int j = 2;j<=x;++j){
            int u; cin >> u;
            hld.modifyPath(last,u,1);
            last = u;
        }
    }
    int ans = 0;
    vector<int> out;
    for(int i = 0;i<N-1;++i){
        if(hld.queryPath(edges[i].f,edges[i].s) >= K){
            ++ans;
            out.push_back(i);
        }
    }
    cout << ans << "\n";
    for(int i = 0;i<out.size();++i){
        if(i != out.size()-1) cout << out[i]+1 << " ";
        else cout << out[i]+1 << "\n";
    }
    return 0;
}

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