Submission #1043505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043505		XRomanticCatX	Railway (BOI17_railway)	C++17	100 / 100	178 ms	64960 KiB

railway

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

#define int long long int

#define pii pair<int , int>

const int MAXN = 1e5 + 10;
const int maxlg = 30;

int h[MAXN];

vector <int> adj[MAXN];

int stft[MAXN][2];

int biparent[MAXN][maxlg];

map <pii , int> eans;

vector <pii> eorder;

int val[MAXN];

int cnt = 1;

vector <int> ansid;

void dfs(int v , int par){
	stft[v][0] = cnt++;
	biparent[v][0] = par;
	for(int i = 1 ; i < maxlg ; i ++){
		biparent[v][i] = biparent[biparent[v][i - 1]][i - 1];
	}
	for(auto u : adj[v]){
		if(u != par){
			h[u] = h[v] + 1;
			dfs(u , v);
		}
	}
	stft[v][1] = cnt++;
}

int LCA(int a , int b){
	if(h[a] < h[b]) swap(a , b);
	for(int i = maxlg - 1 ; i >= 0 ; i--){
		if(h[biparent[a][i]] >= h[b]) a = biparent[a][i]; 
	}
	if(a == b) return a;
	for(int i = maxlg - 1 ; i >= 0 ; i--){
		if(biparent[a][i] != biparent[b][i]){
			a = biparent[a][i] , b = biparent[b][i];
		}
	}
	return biparent[a][0];
}

void Solve(int v, int par){
	for(auto u : adj[v]){
		if(u != par){
			Solve(u , v);
			val[v] += val[u];
			eans[{u , v}] = val[u];
			eans[{v , u}] = val[u];
		}
	}
}

signed main()
{
	int n,m,k;
	cin>>n>>m>>k;
	for(int i = 1 ; i < n ; i ++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
		eorder.push_back({u,v});
	}
	h[1] = 1;
	dfs(1 , 0);
	while(m--){
		int s;
		cin>>s;
		vector <int> v;
		while(s--){
			int x;
			cin>>x;
			v.push_back(x);
		}
		sort(v.begin() , v.end() , [] (int x , int y) {return stft[x][0] < stft[y][0];});
		int fllca = LCA(v[0] , v[v.size() - 1]);
		val[v[0]]++;
		val[v[v.size() - 1]]++;
		val[fllca] -= 2;
		for(int i = 1 ; i < v.size() ;i++){
			int lca = LCA(v[i] , v[i - 1]);
			val[v[i]]++;
			val[v[i - 1]]++;
			val[lca] -= 2;
		} 
	}
	Solve(1 , 0);
	for(int i = 0 ; i < eorder.size() ; i++){
		int f = eorder[i].first;
		int s = eorder[i].second;
		if(eans[{f , s}] >= 2 * k) ansid.push_back(i + 1);
	}
	cout<<ansid.size()<<endl;
	for(auto i : ansid) cout<<i<<" ";
	
}  

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:97:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   for(int i = 1 ; i < v.size() ;i++){
      |                   ~~^~~~~~~~~~
railway.cpp:105:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |  for(int i = 0 ; i < eorder.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