Submission #197125

#	Time	Username	Problem	Language	Result	Execution time	Memory
197125		arnold518	Railway (BOI17_railway)	C++14	100 / 100	406 ms	33312 KiB

railway

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N, M, K;
vector<pii> adj[MAXN+10];
vector<int> A[MAXN+10];
int idx[MAXN+10], cnt, C[MAXN+10];
int par[MAXN+10][30], dep[MAXN+10];

void dfs(int now, int bef, int depth)
{
	par[now][0]=bef; dep[now]=depth;
	idx[now]=++cnt;
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		dfs(nxt.first, now, depth+1);
	}
}

int lca(int u, int v)
{
	int i, j;
	if(dep[u]>dep[v]) swap(u, v);
	for(i=20; i>=0; i--) if(dep[u]<=dep[par[v][i]]) v=par[v][i];
	if(u==v) return u;
	for(i=20; i>=0; i--) if(par[u][i]!=par[v][i]) u=par[u][i], v=par[v][i];
	return par[u][0];
}

vector<int> ans;
void dfs2(int now, int bef, int num)
{
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		dfs2(nxt.first, now, nxt.second);
		C[now]+=C[nxt.first];
	}
	if(num && C[now]>=2*K) ans.push_back(num);
}

int main()
{
	int i, j;

	scanf("%d%d%d", &N, &M, &K);
	for(i=1; i<N; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		adj[u].push_back({v, i});
		adj[v].push_back({u, i});
	}

	dfs(1, 1, 1);
	for(i=1; i<=20; i++) for(j=1; j<=N; j++) par[j][i]=par[par[j][i-1]][i-1];

	for(i=1; i<=M; i++)
	{
		int p;
		scanf("%d", &p);
		for(j=0; j<p; j++) { int t; scanf("%d", &t); A[i].push_back(t); }

		sort(A[i].begin(), A[i].end(), [&](const int &p, const int &q) { return idx[p]<idx[q]; });
		A[i].push_back(A[i][0]);

		for(j=1; j<A[i].size(); j++)
		{
			int p=A[i][j-1], q=A[i][j];
			int w=lca(p, q);
			C[w]--; C[w]--;
			C[p]++; C[q]++;
		}
	}

	dfs2(1, 1, 0);
	printf("%d\n", ans.size());
	sort(ans.begin(), ans.end());
	for(auto it : ans) printf("%d ", it);
}

Compilation message (stderr)

railway.cpp: In function 'int lca(int, int)':
railway.cpp:29:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
railway.cpp: In function 'int main()':
railway.cpp:74:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=1; j<A[i].size(); j++)
            ~^~~~~~~~~~~~
railway.cpp:84:27: 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:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
railway.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~
railway.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &p);
   ~~~~~^~~~~~~~~~
railway.cpp:69:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(j=0; j<p; j++) { int t; scanf("%d", &t); A[i].push_back(t); }
                               ~~~~~^~~~~~~~~~

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