oj.uz

Submission #552227

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

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

		return true;
	}

};


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(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];
			}
		}
	}

	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(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 151 ms 2100 KB Output is correct
2 Correct 170 ms 3064 KB Output is correct
3 Correct 168 ms 3444 KB Output is correct
4 Correct 157 ms 3132 KB Output is correct
5 Correct 168 ms 3208 KB Output is correct
6 Correct 165 ms 3184 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 151 ms 2100 KB Output is correct
2 Correct 170 ms 3064 KB Output is correct
3 Correct 168 ms 3444 KB Output is correct
4 Correct 157 ms 3132 KB Output is correct
5 Correct 168 ms 3208 KB Output is correct
6 Correct 165 ms 3184 KB Output is correct
7 Incorrect 156 ms 2048 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 2028 KB Output is correct
2 Correct 281 ms 37892 KB Output is correct
3 Correct 295 ms 37876 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 153 ms 2028 KB Output is correct
2 Correct 281 ms 37892 KB Output is correct
3 Correct 295 ms 37876 KB Output is correct
4 Incorrect 146 ms 1996 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 160 ms 2208 KB Output is correct
2 Correct 287 ms 39828 KB Output is correct
3 Correct 249 ms 39884 KB Output is correct
4 Execution timed out 3558 ms 39684 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 2208 KB Output is correct
2 Correct 287 ms 39828 KB Output is correct
3 Correct 249 ms 39884 KB Output is correct
4 Execution timed out 3558 ms 39684 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 1996 KB Output is correct
2 Correct 266 ms 35968 KB Output is correct
3 Correct 263 ms 36036 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 1996 KB Output is correct
2 Correct 266 ms 35968 KB Output is correct
3 Correct 263 ms 36036 KB Output is correct
4 Incorrect 140 ms 2048 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 2048 KB Output is correct
2 Correct 265 ms 39876 KB Output is correct
3 Correct 252 ms 39864 KB Output is correct
4 Execution timed out 3573 ms 39644 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 2048 KB Output is correct
2 Correct 265 ms 39876 KB Output is correct
3 Correct 252 ms 39864 KB Output is correct
4 Execution timed out 3573 ms 39644 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 156 ms 2032 KB Output is correct
2 Correct 162 ms 3260 KB Output is correct
3 Correct 161 ms 3296 KB Output is correct
4 Correct 160 ms 3172 KB Output is correct
5 Correct 174 ms 3252 KB Output is correct
6 Correct 159 ms 3268 KB Output is correct
7 Correct 154 ms 2044 KB Output is correct
8 Correct 269 ms 37768 KB Output is correct
9 Correct 259 ms 37776 KB Output is correct
10 Correct 150 ms 2036 KB Output is correct
11 Correct 262 ms 39836 KB Output is correct
12 Correct 249 ms 39852 KB Output is correct
13 Execution timed out 3587 ms 39592 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 156 ms 2032 KB Output is correct
2 Correct 162 ms 3260 KB Output is correct
3 Correct 161 ms 3296 KB Output is correct
4 Correct 160 ms 3172 KB Output is correct
5 Correct 174 ms 3252 KB Output is correct
6 Correct 159 ms 3268 KB Output is correct
7 Correct 154 ms 2044 KB Output is correct
8 Correct 269 ms 37768 KB Output is correct
9 Correct 259 ms 37776 KB Output is correct
10 Correct 150 ms 2036 KB Output is correct
11 Correct 262 ms 39836 KB Output is correct
12 Correct 249 ms 39852 KB Output is correct
13 Execution timed out 3587 ms 39592 KB Time limit exceeded
14 Halted 0 ms 0 KB -