Submission #552227

#	Time	Username	Problem	Language	Result	Execution time	Memory
552227		CpDark	Inside information (BOI21_servers)	C++14	15 / 100	3587 ms	39884 KiB

servers

#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 (stderr)

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
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5