oj.uz

Submission #972249

# Submission time Handle Problem Language Result Execution time Memory
972249 2024-04-30T09:59:40 Z c2zi6 Railway (BOI17_railway) C++14
36 / 100
 107 ms 28348 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

VVPI gp;
VI val;
void increment(int u, int v) {
	val[u]--;
	val[v]++;
}

void getall(int u = 0, int p = -1) {
	for (auto[v, i] : gp[u]) if (v != p) {
		getall(v, u);
		val[u] += val[v];
	}
}

VI paredge;
VI tin, tout;
int tc  = 0;
VVI par; 
void dfs(int u = 0, int p = 0, int pi = -1) {
	tin[u] = tc++;
	paredge[u] = pi;
	par[u][0] = p;
	replr(i, 1, 19) par[u][i] = par[par[u][i-1]][i-1];
	for (auto[v, i] : gp[u]) if (v != p) {
		dfs(v, u, i);
	}
	tout[u] = tc++;
}
bool isanc(int u, int v) {
	return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int LCA(int u, int v) {
	if (isanc(u, v)) return u;
	reprl(i, 19, 0) if (!isanc(par[u][i], v)) u = par[u][i];
	return par[u][0];
}

void solve() {
	int n, m, k;
	cin >> n >> m >> k;
	gp = VVPI(n);
	rep(i, n-1) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		gp[u].pb({v, i});
		gp[v].pb({u, i});
	}
	tin = tout = VI(n);
	par = VVI(n, VI(20));
	paredge = VI(n);
	dfs();

	val = VI(n);
	rep(i, m) {
		int s;
		cin >> s;
		VPI a(s);
		for (auto&[t, u] : a) {
			cin >> u;
			u--;
			t = tin[u];
		}
		sort(all(a));
		rep(i, s) {
			int j = (i+1)%a.size();
			int lca = LCA(a[i].ss, a[j].ss);
			increment(lca, a[i].ss);
			increment(lca, a[j].ss);
			/* cout << lca+1 << " -> " << a[i].ss+1 << endl; */
			/* cout << lca+1 << " -> " << a[j].ss+1 << endl; */
		}
		/* rep(i, s-1) { */
		/* 	int lca = LCA(a[i].ss, a[i+1].ss); */
		/* 	a.pb({tin[lca], lca}); */
		/* } */
		/* sort(all(a)); */
		/*  */
			/* unique */
		/* VPI b{a[0]}; */
		/* for (int i = 1; i < a.size(); i++) if (a[i] != a[i-1]) b.pb(a[i]); */
		/* a = b; */
		/*  */
			/* for (auto&[t, u] : a) cout << u+1 << " "; cout << endl; */
		/* for (auto&[t, u] : a) { */
		/* 	int cur = tin[u]; */
		/* 	while (true) { */
		/* 		auto it = upper_bound(all(a), mkp(cur, (int)+2e9)); */
		/* 		if (it == a.end() || tin[it->ss] > tout[u]) break; */
		/* 		cout << u+1 << " -> " << it->ss+1 << endl; */
		/* 		increment(u, it->ss); */
		/* 		cur = tout[it->ss]; */
		/* 	} */
		/* } */
	}
	getall();
	/* rep(u, n) cout << u+1 << ": " << val[u] << endl; */
	VI ans;
	rep(u, n) if (val[u] >= 2*k) ans.pb(paredge[u]+1);
	cout << ans.size() << endl;
	for (int x : ans) cout << x << " "; cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    /* cin >> t; */
    while (t--) solve();
}

Compilation message

railway.cpp: In function 'void getall(int, int)':
railway.cpp:41:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |  for (auto[v, i] : gp[u]) if (v != p) {
      |           ^
railway.cpp: In function 'void dfs(int, int, int)':
railway.cpp:56:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |  for (auto[v, i] : gp[u]) if (v != p) {
      |           ^
railway.cpp: In function 'void solve()':
railway.cpp:91:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   91 |   for (auto&[t, u] : a) {
      |             ^
railway.cpp:133:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  133 |  for (int x : ans) cout << x << " "; cout << endl;
      |  ^~~
railway.cpp:133:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  133 |  for (int x : ans) cout << x << " "; cout << endl;
      |                                      ^~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 15.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 28128 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 99 ms 27880 KB Output is correct
4 Correct 90 ms 27372 KB Output is correct
5 Correct 58 ms 28148 KB Output is correct
6 Correct 64 ms 28348 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 24660 KB Output is correct
2 Correct 76 ms 21872 KB Output is correct
3 Correct 76 ms 21588 KB Output is correct
4 Correct 76 ms 21480 KB Output is correct
5 Correct 73 ms 21580 KB Output is correct
6 Correct 78 ms 24660 KB Output is correct
7 Correct 71 ms 24732 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 24660 KB Output is correct
2 Correct 76 ms 21872 KB Output is correct
3 Correct 76 ms 21588 KB Output is correct
4 Correct 76 ms 21480 KB Output is correct
5 Correct 73 ms 21580 KB Output is correct
6 Correct 78 ms 24660 KB Output is correct
7 Correct 71 ms 24732 KB Output is correct
8 Correct 69 ms 25004 KB Output is correct
9 Correct 70 ms 24656 KB Output is correct
10 Correct 54 ms 28264 KB Output is correct
11 Correct 57 ms 28104 KB Output is correct
12 Incorrect 58 ms 21188 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

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