oj.uz

Submission #552225

# Submission time Handle Problem Language Result Execution time Memory
552225 2022-04-22T19:45:06 Z CpDark Inside information (BOI21_servers) C++14
20 / 100
 3500 ms 92136 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];
	}
};

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;


bool incresingPath(int a, int b) {
	int p = lca.findLCA(a, b);
	bool oka = true;
	bool okb = true;
	int lasta = -1;
	int lastb = -1;

	if (a != p) {
		int lastw = lca.par[a].second;
		a = lca.par[a].first;
		while (a != p)
		{
			int currw = lca.par[a].second;
			if (currw < lastw) {
				oka = false;
				return false;
			}
			a = lca.par[a].first;
			lastw = currw;
		}
		lasta = lastw;
	}

	if (b != p) {
		int lastw = lca.par[b].second;
		b = lca.par[b].first;
		while (b != p)
		{
			int currw = lca.par[b].second;
			if (currw > lastw) {
				okb = false;
				return false;
			}
			b = lca.par[b].first;
			lastw = currw;
		}
		lastb = lastw;
	}

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

void solve() {
	int n, k;
	cin >> n >> k;
	graph.resize(n + 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);
	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 = incresingPath(b, a);
			}
			if (ans) {
				cout << "yes" << endl;
			}
			else {
				cout << "no" << endl;
			}
		}
		if (t == 'C') {

		}
	}

}


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:165: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]
  165 |   for (int i = 0; i < graph[v].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
servers.cpp: In member function 'int CENTROID::getCentroid(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 function 'void solve()':
servers.cpp:270: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]
  270 |  for (int i = 0; i < queries.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 156 ms 3016 KB Output is correct
2 Correct 159 ms 5416 KB Output is correct
3 Correct 169 ms 5520 KB Output is correct
4 Correct 163 ms 5800 KB Output is correct
5 Correct 182 ms 5928 KB Output is correct
6 Correct 166 ms 5336 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 156 ms 3016 KB Output is correct
2 Correct 159 ms 5416 KB Output is correct
3 Correct 169 ms 5520 KB Output is correct
4 Correct 163 ms 5800 KB Output is correct
5 Correct 182 ms 5928 KB Output is correct
6 Correct 166 ms 5336 KB Output is correct
7 Incorrect 145 ms 3060 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 153 ms 3056 KB Output is correct
2 Correct 425 ms 61272 KB Output is correct
3 Correct 423 ms 61292 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 153 ms 3056 KB Output is correct
2 Correct 425 ms 61272 KB Output is correct
3 Correct 423 ms 61292 KB Output is correct
4 Incorrect 160 ms 3056 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 153 ms 3000 KB Output is correct
2 Correct 511 ms 92068 KB Output is correct
3 Correct 495 ms 92060 KB Output is correct
4 Correct 3063 ms 63764 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 3000 KB Output is correct
2 Correct 511 ms 92068 KB Output is correct
3 Correct 495 ms 92060 KB Output is correct
4 Correct 3063 ms 63764 KB Output is correct
5 Incorrect 145 ms 3020 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 155 ms 3092 KB Output is correct
2 Correct 409 ms 79848 KB Output is correct
3 Correct 459 ms 72724 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 3092 KB Output is correct
2 Correct 409 ms 79848 KB Output is correct
3 Correct 459 ms 72724 KB Output is correct
4 Incorrect 146 ms 2976 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 153 ms 3072 KB Output is correct
2 Correct 534 ms 92124 KB Output is correct
3 Correct 490 ms 91948 KB Output is correct
4 Correct 3091 ms 63808 KB Output is correct
5 Correct 156 ms 3044 KB Output is correct
6 Correct 371 ms 79924 KB Output is correct
7 Correct 462 ms 72664 KB Output is correct
8 Correct 515 ms 79668 KB Output is correct
9 Correct 512 ms 79648 KB Output is correct
10 Correct 1664 ms 66704 KB Output is correct
11 Execution timed out 3587 ms 66560 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 153 ms 3072 KB Output is correct
2 Correct 534 ms 92124 KB Output is correct
3 Correct 490 ms 91948 KB Output is correct
4 Correct 3091 ms 63808 KB Output is correct
5 Correct 156 ms 3044 KB Output is correct
6 Correct 371 ms 79924 KB Output is correct
7 Correct 462 ms 72664 KB Output is correct
8 Correct 515 ms 79668 KB Output is correct
9 Correct 512 ms 79648 KB Output is correct
10 Correct 1664 ms 66704 KB Output is correct
11 Execution timed out 3587 ms 66560 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 152 ms 3192 KB Output is correct
2 Correct 157 ms 5448 KB Output is correct
3 Correct 173 ms 5676 KB Output is correct
4 Correct 162 ms 5836 KB Output is correct
5 Correct 175 ms 5952 KB Output is correct
6 Correct 172 ms 5292 KB Output is correct
7 Correct 150 ms 3132 KB Output is correct
8 Correct 410 ms 61296 KB Output is correct
9 Correct 413 ms 61324 KB Output is correct
10 Correct 155 ms 3052 KB Output is correct
11 Correct 487 ms 92136 KB Output is correct
12 Correct 480 ms 91984 KB Output is correct
13 Correct 3038 ms 63736 KB Output is correct
14 Correct 153 ms 3028 KB Output is correct
15 Correct 383 ms 79868 KB Output is correct
16 Correct 454 ms 72660 KB Output is correct
17 Correct 520 ms 79720 KB Output is correct
18 Correct 513 ms 79676 KB Output is correct
19 Correct 1663 ms 66748 KB Output is correct
20 Execution timed out 3591 ms 66496 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 152 ms 3192 KB Output is correct
2 Correct 157 ms 5448 KB Output is correct
3 Correct 173 ms 5676 KB Output is correct
4 Correct 162 ms 5836 KB Output is correct
5 Correct 175 ms 5952 KB Output is correct
6 Correct 172 ms 5292 KB Output is correct
7 Correct 150 ms 3132 KB Output is correct
8 Correct 410 ms 61296 KB Output is correct
9 Correct 413 ms 61324 KB Output is correct
10 Correct 155 ms 3052 KB Output is correct
11 Correct 487 ms 92136 KB Output is correct
12 Correct 480 ms 91984 KB Output is correct
13 Correct 3038 ms 63736 KB Output is correct
14 Correct 153 ms 3028 KB Output is correct
15 Correct 383 ms 79868 KB Output is correct
16 Correct 454 ms 72660 KB Output is correct
17 Correct 520 ms 79720 KB Output is correct
18 Correct 513 ms 79676 KB Output is correct
19 Correct 1663 ms 66748 KB Output is correct
20 Execution timed out 3591 ms 66496 KB Time limit exceeded
21 Halted 0 ms 0 KB -