oj.uz

Submission #968035

# Submission time Handle Problem Language Result Execution time Memory
968035 2024-04-23T07:07:02 Z NintsiChkhaidze Railway (BOI17_railway) C++17
36 / 100
 174 ms 37564 KB 
#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define int ll
using namespace std;

const int N = 1e5 + 5;
vector <int> v[N];
int timer,tin[N],tout[N],dep[N],d[25][N];
pii a[N];
int fen[N],p[N];

void dfs(int x,int par){
	tin[x] = ++timer;
	d[0][x] = par;
	dep[x] = dep[par] + 1;
	for (int to: v[x])
		if (to != par) dfs(to,x);
	tout[x] = timer;
}

void upd(int idx,int dl){
	while (idx <= 100000){
		fen[idx]+=dl;
		idx+=(idx&(-idx));
	}
}
int get(int idx){
	int s = 0;
	while (idx > 0){
		s += fen[idx];
		idx -= (idx & (-idx));
	}
	return s;
}

int lca(int x,int y){
	if (dep[x] < dep[y]) swap(x,y);
	for (int i = 18; i >= 0; i--)
		if (dep[d[i][x]] >= dep[y]) x = d[i][x];

	if (x == y) return x;
	for (int i = 18; i >= 0; i--)
		if (d[i][x] != d[i][y]) x = d[i][x],y = d[i][y];

	return d[0][x];
}

void updatepath(int x,int y){
	upd(tin[x],+1);
	upd(tin[y],+1);
	upd(tin[lca(x,y)],-2);
}

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int n,m,k;
	cin>>n>>m>>k;

	vector <pii> edges;
	for (int i = 1; i < n; i++){
		int a,b;
		cin>>a>>b;
		v[a].pb(b);
		v[b].pb(a);
		edges.pb({a,b});
	}

	dfs(1,1);
	for (int j = 1; j <= 18; j++)
		for (int i = 1; i <= n; i++)
			d[j][i] = d[j - 1][d[j - 1][i]];

	for (int i=0;i<edges.size();i++){
		int x = edges[i].f,y = edges[i].s;
		if (dep[x] < dep[y]) swap(x,y);
		p[x] = i + 1;
	}

	for (int i = 1; i <= m; i++){
		int t;
		cin>>t;

		for (int j = 1; j <= t; j++){
			cin >> a[j].s;
			a[j].f = tin[a[j].s];
		}

		sort(a+1,a+t+1);
		for (int j = 2; j <= t; j++)
			updatepath(a[j-1].s,a[j].s);
		updatepath(a[t].s,a[1].s);
	}

	vector <int> ans;
	for (int i = 2; i <= n; i++){
		if (get(tout[i]) - get(tin[i] - 1) >= 2*k) ans.pb(p[i]);
	}
	cout<<ans.size()<<endl;
	for (int x: ans)
		cout<<x<<" ";
}

Compilation message

railway.cpp: In function 'int main()':
railway.cpp:78:16: 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]
   78 |  for (int i=0;i<edges.size();i++){
      |               ~^~~~~~~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 23536 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 103 ms 36936 KB Output is correct
2 Correct 5 ms 23388 KB Output is correct
3 Correct 105 ms 36028 KB Output is correct
4 Correct 100 ms 34844 KB Output is correct
5 Correct 174 ms 37096 KB Output is correct
6 Correct 121 ms 37564 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 33100 KB Output is correct
2 Correct 70 ms 30912 KB Output is correct
3 Correct 98 ms 30764 KB Output is correct
4 Correct 94 ms 30776 KB Output is correct
5 Correct 96 ms 30784 KB Output is correct
6 Correct 71 ms 33216 KB Output is correct
7 Correct 60 ms 33216 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 33100 KB Output is correct
2 Correct 70 ms 30912 KB Output is correct
3 Correct 98 ms 30764 KB Output is correct
4 Correct 94 ms 30776 KB Output is correct
5 Correct 96 ms 30784 KB Output is correct
6 Correct 71 ms 33216 KB Output is correct
7 Correct 60 ms 33216 KB Output is correct
8 Correct 161 ms 33364 KB Output is correct
9 Correct 110 ms 33252 KB Output is correct
10 Correct 117 ms 37272 KB Output is correct
11 Correct 146 ms 37312 KB Output is correct
12 Incorrect 166 ms 30684 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

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