oj.uz

Submission #948826

# Submission time Handle Problem Language Result Execution time Memory
948826 2024-03-18T14:59:36 Z koukirocks Railway (BOI17_railway) C++17
23 / 100
 69 ms 28560 KB 
#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
 
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=1e5+10,P=998244353;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;

int n,m,k;
vector<pii> G[MAX];
vector<int> sel[MAX];
int BIT[MAX*2];

void update(int x,int val) {
	while (x<MAX) {
		BIT[x]+=val;
		x+=(-x&x);
	}
}

int query(int x) {
	ll ans=0;
	while (x) {
		ans+=BIT[x];
		x-=(-x&x);
	}
	return ans;
}

int tme=1;
int in[MAX],out[MAX];
int up[MAX][20];
int dep[MAX];

void dfs(int v,int p) {
	dep[v]=dep[p]+1;
	up[v][0]=p;
	for (int i=1;i<20;i++) up[v][i]=up[up[v][i-1]][i-1];
	in[v]=tme++;
	for (auto [i,w]:G[v]) {
		if (i==p) continue;
		dfs(i,v);
	}
	out[v]=tme++;
}

int lca(int a,int b) {
	if (dep[a]<dep[b]) swap(a,b);
	int mv=dep[a]-dep[b];
	for (int i=0;i<20;i++) {
		if (mv&(1<<i)) a=up[a][i];
	}
	if (a==b) return a;
	for (int i=19;i>=0;i--) {
		if (up[a][i]!=up[b][i]) {
			a=up[a][i];
			b=up[b][i];
		}
	}
	return up[a][0];
}

void pth(int a,int b) {
	int ans=lca(a,b);
//	cout<<a<<" "<<b<<" "<<ans<<" abans\n"<<flush;
	update(in[a],1);
	update(in[b],1);
	update(in[ans],-2);
}

void dfs2(int v,int p,int id,vector<int>& ans) {
	if (v!=1 and query(out[v])-query(in[v]-1)>=2*k) ans.push_back(id);
	for (auto [i,w]:G[v]) {
		if (i==p) continue;
		dfs2(i,v,w,ans);
	}
}

int main() {
	speed;
	cin>>n>>m>>k;
	for (int i=1;i<n;i++) {
		int a,b;
		cin>>a>>b;
		G[a].emplace_back(b,i);
		G[b].emplace_back(a,i);
	}
	dep[1]=0;
	dfs(1,1);
//	for (int i=1;i<=n;i++) {
//		cout<<in[i]<<" "<<out[i]<<" inout\n";
//	}
	for (int i=1;i<=m;i++) {
//		cout<<i<<"\n"<<flush;
		int s;
		cin>>s;
		for (int j=0;j<s;j++) {
			int x;
			cin>>x;
			sel[i].push_back(x);
		}
		if (s<=1) continue;
		sort(all(sel[i]),[=](int a,int b) {
			return in[a]<in[b];
		});
		for (int j=0;j<s;j++) {
			pth(sel[i][j],sel[i][(j+1)%s]);
		}
//		for (int i=1;i<=n;i++) {
//			cout<<query(out[i])-query(in[i]-1)<<" ";
//		}
//		cout<<"\n";
	}
//	cout<<"sgfhfh\n"<<flush;
	vector<int> ans;
	dfs2(1,1,0,ans);
//	for (int i=1;i<=n;i++) {
//		cout<<query(out[i])-query(in[i]-1)<<" ";
//	}
//	cout<<"\n";
	cout<<ans.size()<<"\n";
	sort(all(ans));
	for (int i:ans) cout<<i<<" ";
	cout<<"\n";
	return 0;
}


/*
6 3 2
1 3
2 3
3 4
6 4
4 5
4 1 3 2 5
2 6 3
2 3 2
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 6 ms 11100 KB Output is correct
3 Correct 6 ms 11196 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 6 ms 11344 KB Output is correct
7 Correct 6 ms 11096 KB Output is correct
8 Correct 5 ms 11100 KB Output is correct
9 Correct 6 ms 11176 KB Output is correct
10 Correct 3 ms 10648 KB Output is correct
11 Correct 2 ms 10584 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 2 ms 10588 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 6 ms 11100 KB Output is correct
3 Correct 6 ms 11196 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 6 ms 11344 KB Output is correct
7 Correct 6 ms 11096 KB Output is correct
8 Correct 5 ms 11100 KB Output is correct
9 Correct 6 ms 11176 KB Output is correct
10 Correct 3 ms 10648 KB Output is correct
11 Correct 2 ms 10584 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 2 ms 10588 KB Output is correct
15 Correct 26 ms 12016 KB Output is correct
16 Correct 21 ms 11916 KB Output is correct
17 Correct 25 ms 12152 KB Output is correct
18 Correct 7 ms 11608 KB Output is correct
19 Correct 6 ms 11100 KB Output is correct
20 Correct 21 ms 12112 KB Output is correct
21 Correct 24 ms 12152 KB Output is correct
22 Correct 3 ms 10588 KB Output is correct
23 Correct 6 ms 11096 KB Output is correct
24 Correct 6 ms 11100 KB Output is correct
25 Correct 2 ms 10652 KB Output is correct
26 Correct 2 ms 10584 KB Output is correct
27 Correct 6 ms 11500 KB Output is correct
28 Correct 6 ms 11100 KB Output is correct
29 Correct 5 ms 11096 KB Output is correct
30 Correct 5 ms 11096 KB Output is correct
31 Correct 3 ms 10588 KB Output is correct
32 Correct 2 ms 10668 KB Output is correct
33 Correct 2 ms 10584 KB Output is correct
34 Correct 3 ms 10584 KB Output is correct
35 Correct 2 ms 10588 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 16.0

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

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 6 ms 11100 KB Output is correct
3 Correct 6 ms 11196 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 6 ms 11344 KB Output is correct
7 Correct 6 ms 11096 KB Output is correct
8 Correct 5 ms 11100 KB Output is correct
9 Correct 6 ms 11176 KB Output is correct
10 Correct 3 ms 10648 KB Output is correct
11 Correct 2 ms 10584 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 2 ms 10588 KB Output is correct
15 Correct 26 ms 12016 KB Output is correct
16 Correct 21 ms 11916 KB Output is correct
17 Correct 25 ms 12152 KB Output is correct
18 Correct 7 ms 11608 KB Output is correct
19 Correct 6 ms 11100 KB Output is correct
20 Correct 21 ms 12112 KB Output is correct
21 Correct 24 ms 12152 KB Output is correct
22 Correct 3 ms 10588 KB Output is correct
23 Correct 6 ms 11096 KB Output is correct
24 Correct 6 ms 11100 KB Output is correct
25 Correct 2 ms 10652 KB Output is correct
26 Correct 2 ms 10584 KB Output is correct
27 Correct 6 ms 11500 KB Output is correct
28 Correct 6 ms 11100 KB Output is correct
29 Correct 5 ms 11096 KB Output is correct
30 Correct 5 ms 11096 KB Output is correct
31 Correct 3 ms 10588 KB Output is correct
32 Correct 2 ms 10668 KB Output is correct
33 Correct 2 ms 10584 KB Output is correct
34 Correct 3 ms 10584 KB Output is correct
35 Correct 2 ms 10588 KB Output is correct
36 Incorrect 69 ms 28560 KB Output isn't correct
37 Halted 0 ms 0 KB -