oj.uz

답안 #915418

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
915418 2024-01-23T20:58:00 Z starchan Railway (BOI17_railway) C++17
36 / 100
 107 ms 71140 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
#define LOGM (int)18
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
vector<int> adj[MX];
vector<in> edges;
int pa[LOGM][MX];
int tin[MX];
int tout[MX];
int focus[MX];
int timer = 0;
int label[MX];

void dfs(int u, int p)
{
	pa[0][u] = p;
	tin[u] = timer++;
	for(int v: adj[u])
	{
		if(v==p)
			continue;
		dfs(v, u);
	}
	tout[u] = timer;
	return;
}

int lca(int u, int v)
{
	if(tin[u] > tin[v])
		swap(u, v);
	if((tout[u] >= tout[v]))
		return u;
	for(int i = LOGM-1; i >= 0; i--)
	{
		if(tout[pa[i][u]] < tout[v])
			u = pa[i][u];
	}
	return pa[0][u];
}

void dfs2(int u, int p)
{
	for(int v: adj[u])
	{
		if(v==p)
			continue;
		dfs2(v, u);
		focus[u]+=focus[v];
	}
	return;
}

signed main()
{
	fast();
	int n, q, k;
	cin >> n >> q >> k;
	
	int m = n-1;
	while(m--)
	{
		int u, v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
		edges.pb({u, v});
	}

	dfs(1, 0);
	int curr = 0;
	for(auto [x, y]: edges)
	{
		if(tin[x] >= tin[y])
			swap(x, y);
		label[y] = ++curr;
	}

	pa[0][0] = 0;
	tout[0] = INF;
	for(int i = 1; i < LOGM; i++)
	{
		for(int j = 0; j <= n; j++)
			pa[i][j] = pa[i-1][pa[i-1][j]];
	}

	while(q--)
	{
		int M;
		cin >> M;
		vector<in> v;
		for(int QoIGn = 1; QoIGn <= M; QoIGn++)
		{
			int u;
			cin >> u;
			v.pb({tin[u], u});
		}
		sort(v.begin(), v.end());
		for(int i = 0; i < v.size(); i++)
		{
			focus[lca(v[i].s, v[(i+1)%M].s)]--;
			focus[v[i].s]++;
		}
	}
	/*cout << "printign tin[u], tout[u]" << endl;
	for(int u = 1; u <= n; u++)
	{
		printf("tin[%d] = %d, tout[%d] = %d", u, tin[u], u, tout[u]);
		cout << endl;
	}
	cout << "printing lcas NIGELTS" << endl;
	for(int i = 2; i <= n; i++)
	{
		for(int j = i+1; j <= n; j++)
		{
			printf("lca(%d, %d) = %d", i, j, lca(i, j));
			cout << endl;
		}
	}*/
	dfs2(1, 0);
	int cnt = 0;
	vector<int> DOFINQ;
	for(int i = 1; i <= n; i++)
	{
		if(focus[i] >= k)
			DOFINQ.pb(label[i]);
	}
	cout << DOFINQ.size() << "\n";
	for(int ttt: DOFINQ)
		cout << ttt << " ";
	return 0;
}

Compilation message

railway.cpp: In function 'int main()':
railway.cpp:107: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]
  107 |   for(int i = 0; i < v.size(); i++)
      |                  ~~^~~~~~~~~~
railway.cpp:129:6: warning: unused variable 'cnt' [-Wunused-variable]
  129 |  int cnt = 0;
      |      ^~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 48732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 48732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 70812 KB Output is correct
2 Correct 9 ms 48728 KB Output is correct
3 Correct 56 ms 69764 KB Output is correct
4 Correct 50 ms 68804 KB Output is correct
5 Correct 52 ms 70972 KB Output is correct
6 Correct 64 ms 71100 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 66240 KB Output is correct
2 Correct 56 ms 63500 KB Output is correct
3 Correct 72 ms 63040 KB Output is correct
4 Correct 66 ms 61672 KB Output is correct
5 Correct 69 ms 63044 KB Output is correct
6 Correct 64 ms 66360 KB Output is correct
7 Correct 55 ms 66236 KB Output is correct

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 66240 KB Output is correct
2 Correct 56 ms 63500 KB Output is correct
3 Correct 72 ms 63040 KB Output is correct
4 Correct 66 ms 61672 KB Output is correct
5 Correct 69 ms 63044 KB Output is correct
6 Correct 64 ms 66360 KB Output is correct
7 Correct 55 ms 66236 KB Output is correct
8 Correct 70 ms 66492 KB Output is correct
9 Correct 79 ms 66492 KB Output is correct
10 Correct 52 ms 71140 KB Output is correct
11 Correct 52 ms 71096 KB Output is correct
12 Incorrect 107 ms 63320 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 48732 KB Output isn't correct
2 Halted 0 ms 0 KB -