oj.uz

Submission #896526

# Submission time Handle Problem Language Result Execution time Memory
896526 2024-01-01T15:33:38 Z OAleksa Railway (BOI17_railway) C++14
45 / 100
 188 ms 57680 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
const int N = 1e5 + 69;
const int lg = 17;
int up[N][lg];
int n, m, k, tin[N], tout[N], timer;
vector<int> g[N];
set<int> st[N], er[N];
set<tuple<int, int, int>> edges;
vector<int> ans;
bool anc(int v, int u) {
	return tin[v] <= tin[u] && tout[v] >= tout[u];
}
int lca(int a, int b) {
	if (anc(a, b))
		return a;
	else if (anc(b, a))
		return b;
	for (int i = lg - 1;i >= 0;i--) {
		if (!anc(up[a][i], b) && up[a][i] > 0)
			a = up[a][i];
	}
	return up[a][0];
}
void dfs(int v, int p) {
	tin[v] = ++timer;
	up[v][0] = p;
	for (int i = 1;i < lg;i++)
		up[v][i] = up[up[v][i - 1]][i - 1];
	for (auto u : g[v]) {
		if (u == p)
			continue;
		dfs(u, v);
	}
	tout[v] = timer;
}
void solve(int v, int p) {
	for (auto u : g[v]) {
		if (u == p)
			continue;
		solve(u, v);
		if (st[v].size() < st[u].size())
			swap(st[u], st[v]);
		for (auto x : st[u])
			st[v].insert(x);
	}
	for (auto u : er[v]) {
		assert(st[v].count(u) > 0);
		st[v].erase(u);
	}
	if (p != 0) {
		int a = v, b = p;
		if (a > b)
			swap(a, b);
		if (st[v].size() == k) {
			auto u = *edges.lower_bound({a, b, -1});
			ans.push_back(get<2>(u));
		}
		
	}
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
    cin >> n >> m >> k;
    for (int i = 1;i <= n - 1;i++) {
    	int a, b;
    	cin >> a >> b;
    	g[a].push_back(b);
    	g[b].push_back(a);
    	if (a > b)	
    		swap(a, b);
    	edges.insert({a, b, i});
    }
    dfs(1, 0);
    for (int i = 1;i <= m;i++) {
    	int s;
    	cin >> s;
    	vector<int> y(s);
    	for (int j = 0;j < s;j++)
    		cin >> y[j];
    	int lc = y[0];
    	for (int j = 1; j < s;j++)
    		lc = lca(lc, y[j]);
    	er[lc].insert(i);
    	for (int j = 0;j < s;j++) {
    		if (y[j] != lc)
    			st[y[j]].insert(i);
    	}
    }
    solve(1, 0);
    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for (auto u : ans)
    	cout << u << " ";
  }
  return 0;
}

Compilation message

railway.cpp: In function 'void solve(long long int, long long int)':
railway.cpp:58:20: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   58 |   if (st[v].size() == k) {
      |       ~~~~~~~~~~~~~^~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 14936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 14936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 119 ms 57680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 53464 KB Output is correct
2 Correct 176 ms 50004 KB Output is correct
3 Correct 188 ms 55924 KB Output is correct
4 Correct 166 ms 55636 KB Output is correct
5 Correct 166 ms 55792 KB Output is correct
6 Correct 143 ms 53612 KB Output is correct
7 Correct 126 ms 53332 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 53464 KB Output is correct
2 Correct 176 ms 50004 KB Output is correct
3 Correct 188 ms 55924 KB Output is correct
4 Correct 166 ms 55636 KB Output is correct
5 Correct 166 ms 55792 KB Output is correct
6 Correct 143 ms 53612 KB Output is correct
7 Correct 126 ms 53332 KB Output is correct
8 Correct 124 ms 51796 KB Output is correct
9 Correct 125 ms 51808 KB Output is correct
10 Correct 111 ms 57516 KB Output is correct
11 Correct 104 ms 57484 KB Output is correct
12 Correct 76 ms 42884 KB Output is correct
13 Correct 102 ms 43024 KB Output is correct
14 Correct 133 ms 48928 KB Output is correct
15 Correct 138 ms 48976 KB Output is correct
16 Correct 174 ms 56916 KB Output is correct
17 Correct 188 ms 57152 KB Output is correct
18 Correct 162 ms 54916 KB Output is correct
19 Correct 175 ms 50836 KB Output is correct
20 Correct 144 ms 53864 KB Output is correct
21 Correct 140 ms 53748 KB Output is correct
22 Correct 137 ms 53748 KB Output is correct

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 14936 KB Output isn't correct
2 Halted 0 ms 0 KB -