Submission #878289

#	Time	Username	Problem	Language	Result	Execution time	Memory
878289		vjudge1	Martian DNA (BOI18_dna)	C++17	0 / 100	65 ms	104276 KiB

dna

// in the name of God
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define int long long
#define fast() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define GCD(a, b) __gcd(a, b)
#define maxl *max_element
#define minl *min_element
#define ff first
#define ss second
#define pb(x) push_back(x)
#define all(x) x.begin(), x.end()
#define mmt make_pair
#define endl '\n'
#pragma GCC optimize("Ofast")
#pragma GCC optimize("fast-math")
//#pragma GCC target ("avx2")
#pragma GCC optimization ("O4")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 1e9 + 9, maxn = 2e5 + 10, inf = 1e18 + 1, lg = 25, pp = 4447, modd = 1e9 + 9;

int h[maxn], cnt[maxn] = {}, n, m, k;
map<pair<int, int>, int> mp;
vector<vector<int>> g(maxn), par(maxn, vector<int>(lg, -1));
set<int> ans;

void dfs(int v, int p = -1){
	if(v != 0){
		par[v][0] = p;
		for(int i = 1; i < lg; ++i){
			if(par[v][i - 1] != -1) par[v][i] = par[par[v][i - 1]][i - 1];
		}
	}
	for(int u : g[v]){
		if(u != p){
			h[u] = h[v] + 1;
			dfs(u, v);
		}
	}
}
void dfs2(int v, int p = -1){
	for(int u : g[v]){
		if(u != p){
			dfs(u, v);
			if(cnt[u] >= k) ans.insert(mp[mmt(u, v)]);
			cnt[v] += cnt[u];
		}
	}
}
int lca(int v, int u){
	if(v == u) return v;
	if(h[v] < h[u]) swap(v, u);
	for(int i = lg - 1; i >= 0; --i){
		if((1 << i) < (h[v] - h[u]) && par[v][i] != -1){
			v = par[v][i];
		}
	}
	if(v == u) return v;
	for(int i = lg - 1; i >= 0; --i) {
		if(par[v][i] != par[u][i] && par[v][i] != -1 && par[u][i] != -1) {
			v = par[v][i];
			u = par[u][i];
		}
	}
	return par[v][0];
}
bool c(int u, int v) {return h[u] < h[v];}
signed main(){
	fast();
	cin >> n >> m >> k;
	for(int i = 1; i < n; ++i){
		int u, v; cin >> u >> v;
		u--; v--;
		g[u].pb(v);
		g[v].pb(u);
		mp[mmt(u, v)] = i - 1;
		mp[mmt(v, u)] = i - 1;
	}
	dfs(0);
	for(int i = 0; i < m; ++i){
		int nn; cin >> nn;
		vector<int> x;
		for(int j = 0; j < nn; ++j) {int h; cin >> h; x.pb(--h);}
		sort(all(x), c);
		int lcaa = x[0];
		for(int j = 1; j < nn; ++j){
			int lc = lca(x[j - 1], x[j]);
			cnt[x[j - 1]]++;
			cnt[x[j]]++;
			cnt[lc] -= 2;
			lcaa = lca(lcaa, x[j]);
		}
		cnt[x[0]]++;
		cnt[x.back()]++;
		cnt[lcaa] -= 2;
	}
	dfs2(0);
	cout << ans.size() << endl;
	for(int u : ans) cout << u + 1 << " ";
}
// The sea will come out of the darkness
// and the people of the sea will return to their homes
// There is no time left. be sure!!

Compilation message (stderr)

dna.cpp:19: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   19 | #pragma GCC optimization ("O4")
      | 
dna.cpp:20: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   20 | #pragma GCC optimization ("unroll-loops")
      |

• Subtask 1: 0 / 16
• Subtask 2: 0 / 24
• Subtask 3: 0 / 28
• Subtask 4: 0 / 32