oj.uz

Submission #552241

# Submission time Handle Problem Language Result Execution time Memory
552241 2022-04-22T20:41:52 Z CpDark Inside information (BOI21_servers) C++14
15 / 100
 3500 ms 40240 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;

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

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


	inline 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];

		return true;
	}

};


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

	inline 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(log2(n))) + 1;
		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];
			}
		}
	}

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

	inline 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;

inline 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(n + k);
	for (int i = 0; i < n + k - 1; i++) {
		cin >> t;
		if (t == 'S') {
			cin >> a >> b;
			queries[i] = { t,{a,b} };
			graph[a].push_back({ b,timer });
			graph[b].push_back({ a,timer });
			timer++;
		}
		if (t == 'Q') {
			cin >> a >> b;
			queries[i] = { t,{a,b} };
		}
		if (t == 'C') {
			cin >> a;
			queries[i] = { 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 'void LCA::dfs(int, int, int)':
servers.cpp:66: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]
   66 |   for (int i = 0; i < graph[v].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
servers.cpp: In member function 'void CENTROID::dfs(int, int)':
servers.cpp:132: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]
  132 |   for (int i = 0; i < graph[v].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
servers.cpp: In member function 'int CENTROID::getCentroid(int, int)':
servers.cpp:142: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]
  142 |   for (int i = 0; i < graph[v].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
servers.cpp: In function 'void solve()':
servers.cpp:235: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]
  235 |  for (int i = 0; i < queries.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 152 ms 2164 KB Output is correct
2 Correct 164 ms 3316 KB Output is correct
3 Correct 198 ms 3432 KB Output is correct
4 Correct 157 ms 3276 KB Output is correct
5 Correct 165 ms 3276 KB Output is correct
6 Correct 170 ms 3356 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 152 ms 2164 KB Output is correct
2 Correct 164 ms 3316 KB Output is correct
3 Correct 198 ms 3432 KB Output is correct
4 Correct 157 ms 3276 KB Output is correct
5 Correct 165 ms 3276 KB Output is correct
6 Correct 170 ms 3356 KB Output is correct
7 Incorrect 156 ms 2128 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 157 ms 2140 KB Output is correct
2 Correct 306 ms 38008 KB Output is correct
3 Correct 284 ms 38004 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 157 ms 2140 KB Output is correct
2 Correct 306 ms 38008 KB Output is correct
3 Correct 284 ms 38004 KB Output is correct
4 Incorrect 145 ms 2212 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 2276 KB Output is correct
2 Correct 284 ms 39988 KB Output is correct
3 Correct 255 ms 40056 KB Output is correct
4 Execution timed out 3603 ms 39776 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 2276 KB Output is correct
2 Correct 284 ms 39988 KB Output is correct
3 Correct 255 ms 40056 KB Output is correct
4 Execution timed out 3603 ms 39776 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 2220 KB Output is correct
2 Correct 301 ms 36016 KB Output is correct
3 Correct 270 ms 36108 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 2220 KB Output is correct
2 Correct 301 ms 36016 KB Output is correct
3 Correct 270 ms 36108 KB Output is correct
4 Incorrect 162 ms 2220 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 2124 KB Output is correct
2 Correct 264 ms 39988 KB Output is correct
3 Correct 305 ms 39952 KB Output is correct
4 Execution timed out 3568 ms 39900 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 153 ms 2124 KB Output is correct
2 Correct 264 ms 39988 KB Output is correct
3 Correct 305 ms 39952 KB Output is correct
4 Execution timed out 3568 ms 39900 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 153 ms 2116 KB Output is correct
2 Correct 198 ms 3220 KB Output is correct
3 Correct 167 ms 3296 KB Output is correct
4 Correct 157 ms 3200 KB Output is correct
5 Correct 169 ms 3332 KB Output is correct
6 Correct 197 ms 3332 KB Output is correct
7 Correct 151 ms 2156 KB Output is correct
8 Correct 306 ms 37940 KB Output is correct
9 Correct 267 ms 38080 KB Output is correct
10 Correct 153 ms 2224 KB Output is correct
11 Correct 296 ms 40240 KB Output is correct
12 Correct 293 ms 40104 KB Output is correct
13 Execution timed out 3573 ms 39860 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 153 ms 2116 KB Output is correct
2 Correct 198 ms 3220 KB Output is correct
3 Correct 167 ms 3296 KB Output is correct
4 Correct 157 ms 3200 KB Output is correct
5 Correct 169 ms 3332 KB Output is correct
6 Correct 197 ms 3332 KB Output is correct
7 Correct 151 ms 2156 KB Output is correct
8 Correct 306 ms 37940 KB Output is correct
9 Correct 267 ms 38080 KB Output is correct
10 Correct 153 ms 2224 KB Output is correct
11 Correct 296 ms 40240 KB Output is correct
12 Correct 293 ms 40104 KB Output is correct
13 Execution timed out 3573 ms 39860 KB Time limit exceeded
14 Halted 0 ms 0 KB -