oj.uz

Submission #826953

# Submission time Handle Problem Language Result Execution time Memory
826953 2023-08-16T07:23:36 Z 반딧불(#10373) Synchronization (JOI13_synchronization) C++17
100 / 100
 829 ms 64288 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void input();
void solve();
void output();

int main(){
	input();
	solve();
	output();
}

int n, m, q;
int ex[100002], ey[100002];
vector<pair<int, int> > link[100002];
vector<int> timings[100002];
int arr[200002];
int query[200002];
int ans[200002];

void input(){
	scanf("%d %d %d", &n, &m, &q);
	for(int i=1; i<n; i++){
		scanf("%d %d", &ex[i], &ey[i]);
		link[ex[i]].push_back(make_pair(ey[i], i));
		link[ey[i]].push_back(make_pair(ex[i], i));
	}
	for(int i=1; i<=m; i++){
		scanf("%d", &arr[i]);
		timings[arr[i]].push_back(i);
	}
	for(int i=1; i<=q; i++) scanf("%d", &query[i]);
	for(int i=1; i<n; i++) if((int)timings[i].size() % 2) timings[i].push_back(m);
}

bool centroidUsed[200002];
int subTreeSize[200002];

void dfs_subtreeSize(int x, int p){
	subTreeSize[x] = 1;
	for(auto y: link[x]){
		if(centroidUsed[y.first] || y.first == p) continue;
		dfs_subtreeSize(y.first, x);
		subTreeSize[x] += subTreeSize[y.first];
	}
}

int findCentroid(int x, int p, int lim){
	for(auto y: link[x]){
		if(centroidUsed[y.first] || y.first == p) continue;
		if(subTreeSize[y.first] >= lim) return findCentroid(y.first, x, lim);
	}
	return x;
}




/// Union Find

struct UnionFind{
	int par[100002];

	void init(int _n){
		for(int i=1; i<=n; i++) par[i] = i;
	}

	int find(int x){
		if(x==par[x]) return x;
		return par[x] = find(par[x]);
	}

	void merge(int x, int y){
		x = find(x), y = find(y);
		par[y] = x;
	}
} dsu;

void dfsVertices(int x, int p, vector<int> &v){
	v.push_back(x);
	for(auto y: link[x]){
		if(y.first == p || centroidUsed[y.first]) continue;
		dfsVertices(y.first, x, v);
	}
}

int inTime[100002];
void dfs_in(int x, int pe, map<int, int> &mp){
	mp[1] = x;
	for(auto y: link[x]){
		if(centroidUsed[y.first] || y.second == pe || timings[y.second].empty()) continue;
		map<int, int> mp2;
		dfs_in(y.first, y.second, mp2);
		if((int)mp.size() < (int)mp2.size()) mp.swap(mp2);
		for(pair<int, int> p: mp2){
			if(mp.find(p.first) != mp.end()) dsu.merge(mp[p.first], p.second);
			else mp[p.first] = p.second;
		}
		mp2.clear();
	}

	for(int i=0; i<(int)timings[pe].size(); i+=2){
		int s = timings[pe][i], ss = !i ? 0 : timings[pe][i-1] + 1;
		/// [e, ee-1] 범위 내에 있는 모든 수를 합친다
		if(mp.upper_bound(s) == mp.upper_bound(ss-1)) continue;
		while(true){
			auto it = prev(mp.upper_bound(s));
			if(it == mp.begin() || prev(it)->first < ss) break;
			dsu.merge(it->second, prev(it)->second);
			mp.erase(prev(it));
		}
		auto it = prev(mp.upper_bound(s));
		int x = it->second;
		mp.erase(it);
		mp[s] = x;
	}

	while(!mp.empty() && mp.rbegin()->first > timings[pe].back()) mp.erase(prev(mp.end()));

	//printf("Dfs_in %d: ", x);
	//for(pair<int, int> p: mp) printf("(%d, %d) ", p.first, p.second);
	//puts("");
}


int outTime[100002];
void dfs_out(int x, int pe, map<int, int> &mp){
	mp[m] = x;
	for(auto y: link[x]){
		if(centroidUsed[y.first] || y.second == pe || timings[y.second].empty()) continue;
		map<int, int> mp2;
		dfs_out(y.first, y.second, mp2);
		if((int)mp.size() < (int)mp2.size()) mp.swap(mp2);
		for(pair<int, int> p: mp2){
			if(mp.find(p.first) != mp.end()) dsu.merge(mp[p.first], p.second);
			else mp[p.first] = p.second;
		}
		mp2.clear();
	}

	for(int i=0; i<(int)timings[pe].size(); i+=2){
		int e = timings[pe][i+1], ee = (i+2 == (int)timings[pe].size()) ? m+1 : timings[pe][i+2] - 1;
		/// [e, ee-1] 범위 내에 있는 모든 수를 합친다
		if(mp.lower_bound(e) == mp.lower_bound(ee+1)) continue;
		while(true){
			auto it = mp.lower_bound(e);
			if(next(it) == mp.end() || next(it)->first > ee) break;
			dsu.merge(it->second, next(it)->second);
			mp.erase(next(it));
		}
		auto it = mp.lower_bound(e);
		int x = it->second;
		mp.erase(it);
		mp[e] = x;
	}

	while(!mp.empty() && mp.begin()->first < timings[pe][0]) mp.erase(mp.begin());

	//printf("Dfs_out %d: ", x);
	//for(pair<int, int> p: mp) printf("(%d, %d) ", p.first, p.second);
	//puts("");
}


vector<int> subtree[100002], subTreeIn[100002], subTreeOut[100002];

void calculateInCentroid(int c){
	vector<int> vertices;
	dfsVertices(c, -1, vertices);
	for(int x: vertices){
		dsu.par[x] = x, inTime[x] = m+1, outTime[x] = 0;
		subtree[x].clear(), subTreeIn[x].clear(), subTreeOut[x].clear();
	}

	vector<int> inT, outT;

	/// x -> c로 들어오는 시점 찾기
	inTime[c] = 1;
	for(auto y: link[c]){
		if(centroidUsed[y.first]) continue;
		dfsVertices(y.first, c, subtree[y.first]);

		map<int, int> mp;
		for(int x: subtree[y.first]) dsu.par[x] = x;
		if(!timings[y.second].empty()) dfs_in(y.first, y.second, mp);
		for(pair<int, int> p: mp) inTime[p.second] = p.first;
		for(int x: subtree[y.first]){
			inTime[x] = inTime[dsu.find(x)];
			subTreeIn[y.first].push_back(inTime[x]);
			inT.push_back(inTime[x]);
		}

		mp.clear();
		for(int x: subtree[y.first]) dsu.par[x] = x;
		if(!timings[y.second].empty()) dfs_out(y.first, y.second, mp);
		for(pair<int, int> p: mp) outTime[p.second] = p.first;
		for(int x: subtree[y.first]){
			outTime[x] = outTime[dsu.find(x)];
			subTreeOut[y.first].push_back(outTime[x]);
			outT.push_back(outTime[x]);
		}
	}
	inTime[c] = 1, outTime[c] = m;
	inT.push_back(1), outT.push_back(m);

	//printf("Centroid is %d\n", c);
	//for(int v: vertices) printf("Vertex %d: in %d, out %d\n", v, inTime[v], outTime[v]);

	/// 정렬
	sort(inT.begin(), inT.end());
	sort(outT.begin(), outT.end());
	for(int x: vertices){
		sort(subTreeIn[x].begin(), subTreeIn[x].end());
		sort(subTreeOut[x].begin(), subTreeOut[x].end());
	}

	/// 센트로이드 답 업데이트
	ans[c] += upper_bound(inT.begin(), inT.end(), m) - inT.begin();

	/// 각 정점 답 업데이트
	for(auto y: link[c]){
		if(centroidUsed[y.first]) continue;
		for(int x: subtree[y.first]){
			ans[x] += upper_bound(inT.begin(), inT.end(), outTime[x]) - inT.begin();
			ans[x] -= upper_bound(subTreeIn[y.first].begin(), subTreeIn[y.first].end(), outTime[x]) - subTreeIn[y.first].begin();
		}
	}
}

void centroidDecomposition(int x){
	dfs_subtreeSize(x, -1);
	x = findCentroid(x, -1, (subTreeSize[x] + 1) / 2);
	centroidUsed[x] = 1;

	calculateInCentroid(x);

	for(auto y: link[x]){
		if(centroidUsed[y.first]) continue;
		centroidDecomposition(y.first);
	}
}

void solve(){
	centroidDecomposition(1);
}

void output(){
	for(int i=1; i<=q; i++) printf("%d\n", ans[query[i]]);
}

Compilation message

synchronization.cpp: In function 'void input()':
synchronization.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |  scanf("%d %d %d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |   scanf("%d %d", &ex[i], &ey[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   scanf("%d", &arr[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
synchronization.cpp:36:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |  for(int i=1; i<=q; i++) scanf("%d", &query[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 12056 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 12060 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 9 ms 12244 KB Output is correct
7 Correct 40 ms 14464 KB Output is correct
8 Correct 39 ms 14536 KB Output is correct
9 Correct 44 ms 14564 KB Output is correct
10 Correct 541 ms 39528 KB Output is correct
11 Correct 516 ms 39616 KB Output is correct
12 Correct 365 ms 57420 KB Output is correct
13 Correct 135 ms 34848 KB Output is correct
14 Correct 748 ms 39104 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 47884 KB Output is correct
2 Correct 456 ms 49472 KB Output is correct
3 Correct 758 ms 62524 KB Output is correct
4 Correct 781 ms 62460 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 12052 KB Output is correct
3 Correct 6 ms 12060 KB Output is correct
4 Correct 6 ms 12060 KB Output is correct
5 Correct 6 ms 12056 KB Output is correct
6 Correct 9 ms 12372 KB Output is correct
7 Correct 36 ms 16452 KB Output is correct
8 Correct 352 ms 58496 KB Output is correct
9 Correct 352 ms 58500 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 55844 KB Output is correct
2 Correct 749 ms 63836 KB Output is correct
3 Correct 757 ms 64068 KB Output is correct
4 Correct 829 ms 64096 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12084 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 9 ms 12244 KB Output is correct
6 Correct 45 ms 14600 KB Output is correct
7 Correct 509 ms 41164 KB Output is correct
8 Correct 383 ms 58660 KB Output is correct
9 Correct 148 ms 36376 KB Output is correct
10 Correct 693 ms 40520 KB Output is correct
11 Correct 508 ms 51364 KB Output is correct
12 Correct 470 ms 51376 KB Output is correct
13 Correct 798 ms 64288 KB Output is correct