Submission #553342

#	Time	Username	Problem	Language	Result	Execution time	Memory
553342		CpDark	Inside information (BOI21_servers)	C++14	50 / 100	637 ms	93044 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;
	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 (stderr)

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