Submission #135708

#	Time	Username	Problem	Language	Result	Execution time	Memory
135708		khsoo01	Railway (BOI17_railway)	C++11	100 / 100	194 ms	24172 KiB

railway

#include<bits/stdc++.h>
using namespace std;
int n, m, x, sum[100005], a[200005];
int  ord[100005], pord[100005], co;
int dep[100005], spt[20][100005];
vector<int> adj[100005], ans;
vector<pair<int,int> > road;

bool comp (int A, int B) {
	return ord[A] < ord[B];
}

void calc (int cur, int prv) {
	ord[cur] = ++co;
	dep[cur] = dep[prv] + 1;
	spt[0][cur] = prv;
	for(auto &nxt : adj[cur]) {
		if(nxt == prv) continue;
		calc(nxt, cur);
	}
	pord[cur] = co;
}

void wrap (int cur, int prv) {
	for(auto &nxt : adj[cur]) {
		if(nxt == prv) continue;
		wrap(nxt, cur);
		sum[cur] += sum[nxt];
	}
}

int getlca (int A, int B) {
	if(dep[A] < dep[B]) swap(A, B);
	for(int i=20;i--;) {
		if(dep[A] - dep[B] >= (1<<i)) A = spt[i][A];
	}
	if(A == B) return A;
	for(int i=20;i--;) {
		if(spt[i][A] != spt[i][B]) {
			A = spt[i][A]; B = spt[i][B];
		}
	}
	return spt[0][A];
}

bool isanc (int A, int B) {
	return (ord[A] <= ord[B] && pord[B] <= pord[A]);
}

void solve () {
	int N;
	scanf("%d",&N);
	for(int i=1;i<=N;i++) {
		scanf("%d",&a[i]);
	}
	sort(a+1, a+1+N, comp);
	for(int i=1;i<N;i++) {
		a[N+i] = getlca(a[i], a[i+1]);
	}
	sort(a+1, a+2*N, comp);
	vector<int> stk;
	for(int i=1;i<2*N;i++) {
		while(!stk.empty()) {
			if(isanc(stk.back(), a[i])) break;
			else stk.pop_back();
		}
		if(!stk.empty()) {
			sum[stk.back()]--;
			sum[a[i]]++;
		}
		stk.push_back(a[i]);
	}
}

int main()
{
	scanf("%d%d%d",&n,&m,&x);
	for(int i=1;i<n;i++) {
		int A, B;
		scanf("%d%d",&A,&B);
		adj[A].push_back(B);
		adj[B].push_back(A);
		road.push_back({A, B});
	}
	calc(1, 0);
	for(int k=1;k<20;k++) {
		for(int i=1;i<=n;i++) {
			spt[k][i] = spt[k-1][spt[k-1][i]];
		}
	}
	while(m--) solve();
	wrap(1, 0);
	for(int i=0;i<road.size();i++) {
		int A = road[i].first, B = road[i].second;
		int T = (ord[A] > ord[B] ? A : B);
		if(sum[T] >= x) ans.push_back(i+1);
	}
	printf("%d\n",ans.size());
	for(int i=0;i<ans.size();i++) {
		printf("%d ",ans[i]);
	}
	puts("");
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:93:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<road.size();i++) {
              ~^~~~~~~~~~~~
railway.cpp:98:26: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n",ans.size());
                ~~~~~~~~~~^
railway.cpp:99:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ans.size();i++) {
              ~^~~~~~~~~~~
railway.cpp: In function 'void solve()':
railway.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
railway.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
   ~~~~~^~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&m,&x);
  ~~~~~^~~~~~~~~~~~~~~~~~~
railway.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&A,&B);
   ~~~~~^~~~~~~~~~~~~~

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