oj.uz

Submission #553342

# Submission time Handle Problem Language Result Execution time Memory
553342 2022-04-25T14:03:30 Z CpDark Inside information (BOI21_servers) C++14
50 / 100
 637 ms 93044 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
typedef vector<vb> vvb;
const int inf = 1e9 + 7;


struct DSU {
	vi par;
	vi subSize;
	vector<set<int>> data;

	void init(int n) {
		par.resize(n + 1);
		subSize.resize(n + 1);
		data.resize(n + 1);
		for (int i = 1; i <= n; i++) {
			par[i] = i;
			subSize[i] = 1;
			data[i].insert(i);
		}
	}

	int findSet(int v) {
		if (v == par[v]) return v;
		return findSet(par[v]);
	}


	bool unite(int v, int u) {
		int pv = findSet(v);
		int pu = findSet(u);
		if (pv == pu)return false;

		if (subSize[pv] > subSize[pu]) swap(pv, pu);
		par[pv] = pu;
		subSize[pu] += subSize[pv];


		bool swaped = false;
		if (data[pv].size() > data[pu].size()) {
			swap(pv, pu);
			swaped = true;
		}

		auto it = data[pv].begin();
		for (int i = 0; i < data[pv].size(); i++) {
			data[pu].insert(*it);
			it++;
		}

		if (swaped) {
			swap(data[pv], data[pu]);
		}

		return true;
	}

	bool query(int v, int d) {
		int pv = findSet(v);

		auto it = data[pv].find(d);
		if (it == data[pv].end()) return false;
		return true;
	}

	int count(int d) {
		int pv = findSet(d);
		int ans = subSize[pv];
		return ans;
	}
};


struct LCA {
	vvp graph;
	vvi table;
	vi timeIn;
	vi timeOut;
	vp par;
	int log;
	int timer = 0;

	void dfs(int v, int p, int w) {
		par[v] = { p,w };
		table[v][0] = p;
		timeIn[v] = timer;
		timer++;

		for (int i = 0; i < graph[v].size(); i++) {
			int u = graph[v][i].first;
			int w = graph[v][i].second;
			if (u != p) {
				dfs(u, v, w);
			}
		}

		timeOut[v] = timer;
		timer++;
	}


	void preCalc(int root, int n, vvp& g) {
		log = ceil(log2(n));
		graph = g;
		timeIn.resize(n + 1);
		timeOut.resize(n + 1);
		par.resize(n + 1);
		table.resize(n + 1, vi(log + 1));
		timer = 0;

		dfs(root, root, -1);
		for (int i = 1; i <= log; i++) {
			for (int v = 1; v <= n; v++) {
				int p = table[v][i - 1];
				table[v][i] = table[p][i - 1];
			}
		}
	}

	bool isAncestor(int a, int b) {
		if (timeIn[a] <= timeIn[b] && timeOut[a] >= timeOut[b]) {
			return true;
		}
		return false;
	}

	int findLCA(int a, int b) {
		if (isAncestor(a, b))return a;
		if (isAncestor(b, a))return b;

		for (int i = log; i >= 0; i--) {
			if (!isAncestor(table[a][i], b)) {
				a = table[a][i];
			}
		}
		return table[a][0];
	}
	

	int lastw(int from, int to) {
		for (int i = log; i >= 0; i--) {
			if (!isAncestor(table[from][i], to)) {
				from = table[from][i];
			}
		}
		return par[from].second;
	}
};

struct CENTROID
{
	vvp graph;
	vi subSize;
	int n;

	void init(int N, vvp& g) {
		n = N;
		graph = g;
		subSize.resize(n + 1);
		dfs(1, 1);
	}

	void dfs(int v, int p) {
		subSize[v] = 1;
		for (int i = 0; i < graph[v].size(); i++) {
			int u = graph[v][i].first;
			if (u != p) {
				dfs(u, v);
				subSize[v] += subSize[u];
			}
		}
	}

	int getCentroid(int v, int p) {
		for (int i = 0; i < graph[v].size(); i++) {
			int u = graph[v][i].first;
			if (u != p && subSize[u] > n / 2) {
				return getCentroid(u, v);

			}
		}
		return v;
	}

};

vvp graph;
LCA lca;
vi topUpI;
vi topUpD;

int dfscount(int v, int p, int lasttime) {
	int sum = 1;

	for (int i = 0; i < graph[v].size(); i++) {
		int u = graph[v][i].first;
		int time = graph[v][i].second;
		if (u != p && time > lasttime) {
			int curr = dfscount(u, v, time);
			sum += curr;
		}
	}
	return sum;
}


bool path(int a, int b) {
	int p = lca.findLCA(a, b);
	bool oka = false;
	bool okb = false;

	int topa = topUpD[a];
	int topb = topUpI[b];

	if (lca.isAncestor(topa, p)) oka = true;
	if (lca.isAncestor(topb, p)) okb = true;
	if (!oka || !okb) return false;

	int lasta = -1;
	int lastb = -1;

	if (a != p) {
		lasta = lca.lastw(a, p);
	}
	if (b != p) {
		lastb = lca.lastw(b, p);
	}

	if (lasta != -1 && lastb != -1 && lastb > lasta) return false;
	if (oka && okb) return true;
	return false;
}



void dfs(int v, int p, int wp) {

	for (int i = 0; i < graph[v].size(); i++) {
		int u = graph[v][i].first;
		int w = graph[v][i].second;

		if (u != p) {
			if (wp != -1 && w < wp) {
				topUpI[u] = topUpI[v];
			}
			else {
				topUpI[u] = v;
			}

			if (wp != -1 && w > wp) {
				topUpD[u] = topUpD[v];
			}
			else {
				topUpD[u] = v;
			}

			dfs(u, v, w);
		}
	}
}


void solve() {
	int n, k;
	cin >> n >> k;
	graph.resize(n + 1);
	topUpI.resize(n + 1, -1);
	topUpD.resize(n + 1, -1);

	DSU dsu;
	dsu.init(n);
	char t;
	int a, b;
	int timer = 1;

	vector<pair<char, pii>> queries;
	for (int i = 0; i < n + k - 1; i++) {
		cin >> t;
		if (t == 'S') {
			cin >> a >> b;
			queries.push_back({ t,{a,b} });
			graph[a].push_back({ b,timer });
			graph[b].push_back({ a,timer });
			timer++;
		}
		if (t == 'Q') {
			cin >> a >> b;
			queries.push_back({ t,{a,b} });
		}
		if (t == 'C') {
			cin >> a;
			queries.push_back({ t,{a,a} });
		}
	}

	CENTROID c;
	c.init(n, graph);
	int centroid = c.getCentroid(1, 1);
	topUpI[centroid] = centroid;
	topUpD[centroid] = centroid;

	dfs(centroid, centroid, -1);
	lca.preCalc(centroid, n, graph);

	for (int i = 0; i < queries.size(); i++) {
		t = queries[i].first;
		a = queries[i].second.first;
		b = queries[i].second.second;

		if (t == 'S') {
			dsu.unite(a, b);
		}
		if (t == 'Q') {
			bool connected = dsu.findSet(a) == dsu.findSet(b);
			bool ans = false;
			if (connected) {
				ans = path(a, b);
			}
			if (ans) {
				cout << "yes" << endl;
			}
			else {
				cout << "no" << endl;
			}
		}
		if (t == 'C') {
			int ans = dfscount(a, a, -1);
			cout << ans << endl;
		}
	}

}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	solve();

	return 0;
}

Compilation message

servers.cpp: In member function 'bool DSU::unite(int, int)':
servers.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for (int i = 0; i < data[pv].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
servers.cpp: In member function 'void LCA::dfs(int, int, int)':
servers.cpp:99:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for (int i = 0; i < graph[v].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
servers.cpp: In member function 'void CENTROID::dfs(int, int)':
servers.cpp:175:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |   for (int i = 0; i < graph[v].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
servers.cpp: In member function 'int CENTROID::getCentroid(int, int)':
servers.cpp:185:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |   for (int i = 0; i < graph[v].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
servers.cpp: In function 'int dfscount(int, int, int)':
servers.cpp:205:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  205 |  for (int i = 0; i < graph[v].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~
servers.cpp: In function 'void dfs(int, int, int)':
servers.cpp:248:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  248 |  for (int i = 0; i < graph[v].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~
servers.cpp: In function 'void solve()':
servers.cpp:315:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<char, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  315 |  for (int i = 0; i < queries.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 165 ms 3008 KB Output is correct
2 Correct 175 ms 5452 KB Output is correct
3 Correct 206 ms 5476 KB Output is correct
4 Correct 189 ms 5860 KB Output is correct
5 Correct 202 ms 6020 KB Output is correct
6 Correct 198 ms 5412 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 165 ms 3008 KB Output is correct
2 Correct 175 ms 5452 KB Output is correct
3 Correct 206 ms 5476 KB Output is correct
4 Correct 189 ms 5860 KB Output is correct
5 Correct 202 ms 6020 KB Output is correct
6 Correct 198 ms 5412 KB Output is correct
7 Incorrect 167 ms 3004 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 162 ms 3076 KB Output is correct
2 Correct 601 ms 62296 KB Output is correct
3 Correct 548 ms 62244 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 162 ms 3076 KB Output is correct
2 Correct 601 ms 62296 KB Output is correct
3 Correct 548 ms 62244 KB Output is correct
4 Incorrect 161 ms 3320 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 2988 KB Output is correct
2 Correct 567 ms 93012 KB Output is correct
3 Correct 554 ms 93012 KB Output is correct
4 Correct 382 ms 64900 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 2988 KB Output is correct
2 Correct 567 ms 93012 KB Output is correct
3 Correct 554 ms 93012 KB Output is correct
4 Correct 382 ms 64900 KB Output is correct
5 Incorrect 170 ms 3040 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 3108 KB Output is correct
2 Correct 422 ms 80740 KB Output is correct
3 Correct 544 ms 73732 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 3108 KB Output is correct
2 Correct 422 ms 80740 KB Output is correct
3 Correct 544 ms 73732 KB Output is correct
4 Incorrect 158 ms 3044 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 167 ms 2992 KB Output is correct
2 Correct 564 ms 93044 KB Output is correct
3 Correct 553 ms 92924 KB Output is correct
4 Correct 389 ms 64696 KB Output is correct
5 Correct 160 ms 3148 KB Output is correct
6 Correct 415 ms 80860 KB Output is correct
7 Correct 494 ms 73732 KB Output is correct
8 Correct 576 ms 80868 KB Output is correct
9 Correct 636 ms 80540 KB Output is correct
10 Correct 591 ms 68132 KB Output is correct
11 Correct 586 ms 68532 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 167 ms 2992 KB Output is correct
2 Correct 564 ms 93044 KB Output is correct
3 Correct 553 ms 92924 KB Output is correct
4 Correct 389 ms 64696 KB Output is correct
5 Correct 160 ms 3148 KB Output is correct
6 Correct 415 ms 80860 KB Output is correct
7 Correct 494 ms 73732 KB Output is correct
8 Correct 576 ms 80868 KB Output is correct
9 Correct 636 ms 80540 KB Output is correct
10 Correct 591 ms 68132 KB Output is correct
11 Correct 586 ms 68532 KB Output is correct
12 Incorrect 162 ms 3056 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 175 ms 3208 KB Output is correct
2 Correct 197 ms 5456 KB Output is correct
3 Correct 190 ms 5544 KB Output is correct
4 Correct 178 ms 5840 KB Output is correct
5 Correct 186 ms 5960 KB Output is correct
6 Correct 230 ms 5376 KB Output is correct
7 Correct 160 ms 3212 KB Output is correct
8 Correct 525 ms 62272 KB Output is correct
9 Correct 485 ms 62308 KB Output is correct
10 Correct 195 ms 3136 KB Output is correct
11 Correct 533 ms 92960 KB Output is correct
12 Correct 625 ms 92924 KB Output is correct
13 Correct 400 ms 64688 KB Output is correct
14 Correct 166 ms 3056 KB Output is correct
15 Correct 432 ms 80840 KB Output is correct
16 Correct 522 ms 73616 KB Output is correct
17 Correct 604 ms 80756 KB Output is correct
18 Correct 637 ms 80608 KB Output is correct
19 Correct 547 ms 68292 KB Output is correct
20 Correct 543 ms 68476 KB Output is correct
21 Correct 540 ms 63704 KB Output is correct
22 Correct 563 ms 65392 KB Output is correct
23 Correct 534 ms 71532 KB Output is correct
24 Correct 576 ms 73164 KB Output is correct
25 Correct 634 ms 80280 KB Output is correct
26 Correct 531 ms 85656 KB Output is correct
27 Correct 515 ms 87136 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 175 ms 3208 KB Output is correct
2 Correct 197 ms 5456 KB Output is correct
3 Correct 190 ms 5544 KB Output is correct
4 Correct 178 ms 5840 KB Output is correct
5 Correct 186 ms 5960 KB Output is correct
6 Correct 230 ms 5376 KB Output is correct
7 Correct 160 ms 3212 KB Output is correct
8 Correct 525 ms 62272 KB Output is correct
9 Correct 485 ms 62308 KB Output is correct
10 Correct 195 ms 3136 KB Output is correct
11 Correct 533 ms 92960 KB Output is correct
12 Correct 625 ms 92924 KB Output is correct
13 Correct 400 ms 64688 KB Output is correct
14 Correct 166 ms 3056 KB Output is correct
15 Correct 432 ms 80840 KB Output is correct
16 Correct 522 ms 73616 KB Output is correct
17 Correct 604 ms 80756 KB Output is correct
18 Correct 637 ms 80608 KB Output is correct
19 Correct 547 ms 68292 KB Output is correct
20 Correct 543 ms 68476 KB Output is correct
21 Correct 540 ms 63704 KB Output is correct
22 Correct 563 ms 65392 KB Output is correct
23 Correct 534 ms 71532 KB Output is correct
24 Correct 576 ms 73164 KB Output is correct
25 Correct 634 ms 80280 KB Output is correct
26 Correct 531 ms 85656 KB Output is correct
27 Correct 515 ms 87136 KB Output is correct
28 Incorrect 176 ms 3016 KB Extra information in the output file
29 Halted 0 ms 0 KB -