Submission #851036

#	Time	Username	Problem	Language	Result	Execution time	Memory
851036		LCJLY	Railway (BOI17_railway)	C++14	100 / 100	291 ms	58260 KiB

railway

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

#define int long long
#define show(x,y) //cout << y << " " << #x << "\n";
#define show2(x,y,i,j) //cout << y << " " << #x << "  " << j << " " << #i << "\n";
typedef pair<int,int>pii;

void solve(){
}

int n,m,k;
vector<pii>adj[100005];
int color[100005];

const int MAXN = 100050;
const int LOGN = 17;
int p[LOGN+1][MAXN], h[MAXN];   //h: number of edges from root
long long d[MAXN];     //dist: sum of edge weight from root
bitset<MAXN> visited;
void dfs(int x) {
    if (visited[x]) return;
    visited[x] = 1;
    for (int k = 0; k < LOGN; ++k) {
        if (p[k][x] == -1) break;
        p[k+1][x] = p[k][p[k][x]];
    }
    for (auto it:adj[x]) {
        if (visited[it.first]) continue;
        p[0][it.first] = x;
        d[it.first] = d[x] + 1;
        h[it.first] = h[x] + 1;
        color[it.first]=it.second;
        dfs(it.first);
    }
}

/* Query */
int lca(int a, int b) { //h[a] < h[b]
    if (h[a] > h[b]) swap(a, b);
    /* advance b by h[b] - h[a] parents */
    for (int k = 0, d = h[b] - h[a]; k < LOGN; ++k) {
        if (d & (1<<k))  b = p[k][b];
    }
    if (a == b) return a;
    assert(h[a] == h[b]); //same height
    /* to be continued */
    for (int k = LOGN-1; k >= 0; --k) {
        if (p[k][a] != p[k][b]) 
            a = p[k][a], b = p[k][b];
    }
    assert(p[0][a] == p[0][b]);        //same immediate parent
    return p[0][a];
}

set<pii>storage[100005]; //end ind
vector<int>ans;

void dp(int index, int par){
	for(auto it:adj[index]){
		if(it.first==par) continue;
		dp(it.first,index);
		show(neigh,it.first);
		if(storage[it.first].size()>storage[index].size()) swap(storage[it.first],storage[index]);
		
		for(auto it2:storage[it.first]) storage[index].insert(it2);
	}
	show(visit,index);
	//remove end nodes
	auto ite=storage[index].lower_bound({index,0});
	while(ite!=storage[index].end()&&ite->first==index){
		storage[index].erase(ite);
		ite=storage[index].lower_bound({index,0});
	}
	
	if(storage[index].size()>=k){
		ans.push_back(color[index]);
	}
}

int32_t main(){
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	
	cin >> n >> m >> k;
	
	int temp,temp2;
	for(int x=0;x<n-1;x++){
		cin >> temp >> temp2;
		adj[temp].push_back({temp2,x+1});
		adj[temp2].push_back({temp,x+1});
	}
	
	dfs(1);
	
	show(done,1);
	
	for(int x=0;x<m;x++){
		cin >> temp;
		vector<int>v;
		for(int y=0;y<temp;y++){
			cin >> temp2;
			v.push_back(temp2);
		}
		
		int ancestor=v[0];
		for(int y=1;y<temp;y++){
			ancestor=lca(ancestor,v[y]);
		}
		
		for(int y=0;y<temp;y++){
			storage[v[y]].insert({ancestor,x});
		}
	}	
	
	show(done,2);
	
	dp(1,-1);
	
	show(done,3);
	
	sort(ans.begin(),ans.end());
	cout << ans.size() << "\n";
	for(auto it:ans){
		cout << it << " ";
	}
	
}

Compilation message (stderr)

railway.cpp: In function 'void dp(long long int, long long int)':
railway.cpp:76:26: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   76 |  if(storage[index].size()>=k){
      |     ~~~~~~~~~~~~~~~~~~~~~^~~

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