oj.uz

Submission #907540

# Submission time Handle Problem Language Result Execution time Memory
907540 2024-01-15T20:26:02 Z Nonoze Spring cleaning (CEOI20_cleaning) C++17
35 / 100
 286 ms 80076 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define sz(x) (int)(x.size())
const int LOG=25;

int n, q;
vector<vector<int>> adj;
vector<vector<int>> m;
vector<int> depth;
vector<int> a;
vector<int> empls;
vector<int> numerotation;
vector<vector<int>> graph;
map<int, int> mp;
vector<int> prefix;
vector<int> parity;
vector<int> parent;
vector<pair<int, int>> isin;
int cntleaf=0, tot=0;
int ans=0;

void dfsdepth(int s, int lst, int &act) {
	isin[s].first=act++;
	if (adj[s].size()==1) prefix[s]++;
	for (auto u: adj[s]) {
		if (u==lst) continue;
		parent[u]=s;
		depth[u]=depth[s]+1;
		dfsdepth(u, s, act);
		prefix[s]+=prefix[u];
		a.push_back(s);
		a.push_back(u);
	}
	isin[s].second=act++;
	return;
}

void dfsparity(int s, int lst=-1) {
	for (auto u: adj[s]) {
		if (u==lst) continue;
		parity[u]=parity[s]+(prefix[u]+1)%2;
		dfsparity(u, s);
	}
	if (lst==-1) tot+=n-1;
	else tot+=(prefix[s]+1)%2;
	return;
}

int dfstot(int s, int lst) {
	int comp=mp[s];
	for (auto u: graph[s]) {
		comp+=dfstot(u, s);
	}
	if (sz(adj[s])<2) comp++;
	if (comp%2==1) {
		int temp=parity[s], d=depth[s];
		if (lst>=0) temp-=parity[lst], d-=depth[lst];
		ans-=temp;
		ans+=d-temp;
	}
	if (sz(adj[s])<2) comp--;
	return comp;
}

void sparsetable() {
	m.clear();
	m.resize(sz(a)+5, vector<int>(LOG, 0));
	for (int i=0; i<sz(a); i++) {
		if (empls[a[i]]==-1) empls[a[i]]=i;
		m[i][0]=a[i];
	}
	for (int k=1; k<LOG; k++) {
		for (int i=0; i+(1<<k)-1 < n; i++) {
			m[i][k]=min(m[i][k-1], m[i+(1<<(k-1))][k-1]);
		}
	}
}

int lca(int u, int v) {
	int l=empls[u], r=empls[v];
	if (l>r) swap(l, r);
	int len=r-l+1, k=log2(len);
	return min(m[l][k], m[r-(1<<k)+1][k]);
}


int ALLPROBLEM() {
	int lst=cntleaf;
	while(q--) {
		cntleaf=lst;
		int d; cin >> d;
		mp.clear();
		vector<pair<int, int>> change(d);
		for (auto &u: change) {
			cin >> u.second, u.second--;
			u.second=numerotation[u.second];
			u.first=isin[u.second].first;
			if (sz(adj[u.second])>1 || mp[u.second]) cntleaf++;
			mp[u.second]++;
		}
		if (cntleaf%2==1) {
			cout << -1 << endl;
			continue;
		}
		sort(change.begin(), change.end());
		set<int> L;
		for (auto u: change) {
			if (L.empty()) {
				L.insert(u.second);
				continue;
			}
			auto next=L.upper_bound(u.second);
			if (next==L.end()) next--;
			auto prec=L.lower_bound(u.second);
			if (prec!=L.begin()) prec--;
			L.insert(u.second);
			L.insert(lca(u.second, *prec));
			L.insert(lca(u.second, *next));
		}
		vector<pair<int, int>> vec;
		for (auto u=L.begin(); u!=L.end(); u++) {
			vec.push_back({isin[*u].first, *u});
		}
		sort(vec.begin(), vec.end());
		stack<int> act;
		act.push(vec[0].second);
		for (int i=1; i<sz(vec); i++) {
			int u=vec[i].second;
			while (isin[act.top()].second<isin[u].first) act.pop();
			graph[act.top()].push_back(u);
			act.push(vec[i].second);
		}
		ans=tot+d;
		dfstot(vec[0].second, 0);
		cout << ans << endl;
		for (auto u: vec) graph[u.second].clear();
	}
	return 0;
}

int solve() {
	cin >> n >> q;
	adj.resize(n);
	graph.resize(n);
	numerotation.resize(n);
	empls.resize(n, -1);
	depth.resize(n, 0);
	prefix.resize(n, 0);
	parity.resize(n, 0);
	isin.resize(n);
	parent.resize(n);
	for (int i=0; i<n-1; i++) {
		int u, v; cin >> u >> v;
		u--, v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (auto u: adj) if (sz(u)==1) cntleaf++;
	int begining=0;
	while (sz(adj[begining])<2) begining++;
	queue<pair<int, int>> myqueue;
	myqueue.push({begining, -1});
	int act=0;
	while (!myqueue.empty()) {
		int s=myqueue.front().first, lst=myqueue.front().second; myqueue.pop();
		numerotation[s]=act++;
		for (auto &u: adj[s]) {
			if (u!=lst) myqueue.push({u, s});
		}
	}
	vector<vector<int>> newadj=adj;
	adj.clear();
	adj.resize(n);
	for (int i=0; i<n; i++) {
		adj[numerotation[i]]=newadj[i];
		for (auto &u: adj[numerotation[i]]) {
			u=numerotation[u];
		}
	}
	int temp=0;
	dfsdepth(0, -1, temp);

	dfsparity(0);

	sparsetable();
	return ALLPROBLEM();
}


signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 124 ms 15568 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4440 KB Output is correct
2 Correct 25 ms 4188 KB Output is correct
3 Correct 125 ms 70184 KB Output is correct
4 Correct 173 ms 58204 KB Output is correct
5 Correct 243 ms 80076 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 6740 KB Output is correct
2 Correct 20 ms 5980 KB Output is correct
3 Correct 111 ms 75424 KB Output is correct
4 Correct 217 ms 79748 KB Output is correct
5 Correct 113 ms 68544 KB Output is correct

Subtask #4
0 / 16.0

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

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 45440 KB Output is correct
2 Incorrect 199 ms 46532 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 70084 KB Output is correct
2 Correct 257 ms 72160 KB Output is correct
3 Correct 257 ms 72456 KB Output is correct
4 Correct 286 ms 71872 KB Output is correct

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 124 ms 15568 KB Output isn't correct
3 Halted 0 ms 0 KB -