Submission #878129

#	Time	Username	Problem	Language	Result	Execution time	Memory
878129		vjudge1	Railway (BOI17_railway)	C++17	0 / 100	1064 ms	64152 KiB

railway

// 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 = 1e6 + 10, inf = 1e18 + 1, lg = 25, pp = 4447, modd = 1e9 + 9;

int par[maxn][lg], h[maxn];
map<pair<int, int>, int> mp;
vector<vector<int>> g(maxn);
vector<pair<int, int>> e;

void dfs(int v, int p = -1){
	if(v != 0){
		par[v][0] = p;
		for(int i = 1;i < lg; ++i){
			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);
		}
	}
}
int lca(int v, int u){
	if(v == u) return v;
	if(h[v] < h[u]) swap(v, u);
	for(int i = 0; i < lg; ++i){
		if((1 << i) & (h[v] - h[u])){
			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];
}
signed main(){
	fast();
	int n, m, k; 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);
		e.pb(mmt(u, v));
	}
	dfs(0);
	for(int i = 0; i < m; ++i){
		int nn; cin >> nn;
		int last, x;
		for(int i = 0; i < nn; ++i){
			cin >> x;
			x--;
			if(i == 0) last = x;
			else{
				int lc = lca(x, last);
				int x2 = x, last2 = last;
				while(x2 != lc){
					mp[mmt(par[x2][0], x2)]++;
					x2 = par[x2][0];
				}
				while(last2 != lc){
					mp[mmt(par[last2][0], last2)]++;
					last2 = par[last2][0];
				}
				last = x;
			}
		}
	}
	int c = 0;
	for(auto [x, y] : e){
		int kk = mp[mmt(x, y)] + mp[mmt(y, x)];
		if(kk >= k) cout << c + 1 << " ";
		c++;
	}
}
// 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)

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

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