Submission #924266

#	Time	Username	Problem	Language	Result	Execution time	Memory
924266		42kangaroo	Inside information (BOI21_servers)	C++17	100 / 100	941 ms	77840 KiB

servers

//
// Created by 42kangaroo on 07/02/2024.
//
#include "bits/stdc++.h"

using namespace std;

template<typename T>
using g_t = vector<vector<T>>;

struct Que {
	char c;
	int f, s;
	string an;
};

struct BinL {
	bool asc, desc;
	int p, upVal, downVal;
};

struct Ed {
	int a, b, w;
};

struct FenT {
	vector<int> a, cooC;

	void inc(int k, int v) {
		int p = std::lower_bound(cooC.begin(), cooC.end(), k) - cooC.begin();
		for (int i = p + 1; i < a.size(); i += i & -i) {
			a[i] += v;
		}
	}

	int get(int k) {
		int res = 0;
		if (k < 0) return 0;
		int p = std::lower_bound(cooC.begin(), cooC.end(), k) - cooC.begin();
		for (int i = p + 1; i > 0; i -= i & -i) {
			res += a[i];
		}
		return res;
	}

};

array<int, 120005> logT;
g_t<BinL> binL;
g_t<Ed> g;
vector<int> de;
vector<int> pCD;
vector<int> dCD;
vector<FenT> fCD;

void dfs(int n, int p, int d, vector<pair<int, int>> &pa) {
	pa[n].first = p;
	de[n] = d;
	for (auto &e: g[n]) {
		if (e.b == p) {
			pa[n].second = e.w;
			continue;
		}
		dfs(e.b, n, d + 1, pa);
	}
}

BinL combine(const BinL &l, const BinL &r) {
	BinL res{};
	res.p = r.p;
	res.upVal = r.upVal;
	res.downVal = l.downVal;
	res.asc = l.asc && r.asc && l.upVal > r.downVal;
	res.desc = l.desc && r.desc && l.upVal < r.downVal;
	return res;
}

BinL reverse(const BinL& in) {
	BinL res{};
	res.p = -1;
	res.upVal = in.downVal;
	res.downVal = in.upVal;
	res.asc = in.desc;
	res.desc = in.asc;
	return res;
}

void binLPrep(vector<pair<int, int>> &p) {
	binL = g_t<BinL>(logT[p.size()] + 1, vector<BinL>(p.size()));
	for (int i = 0; i < p.size(); ++i) {
		binL[0][i] = {true, true, p[i].first, p[i].second, p[i].second};
	}
	for (int i = 1; i < binL.size(); ++i) {
		for (int j = 0; j < p.size(); ++j) {
			binL[i][j] = combine(binL[i - 1][j], binL[i - 1][binL[i - 1][j].p]);
		}
	}
}

pair<bool, BinL> connected(int i, int st, int en) {
	if (st == en) return {true, {true, true, -1, -1, -1}};
	bool sw = false;
	if (de[st] < de[en]) {
		sw = true;
		swap(st, en);
	}
	int k = de[st] - de[en];
	BinL biSt{true, true, -1, -1, -1};
	BinL biEn{true, true, -1, -1, -1};
	for (int j = 0; k; k >>= 1, ++j) {
		if (k & 1) {
			if (biSt.p == -1) {
				biSt = binL[j][st];
			} else {
				biSt = combine(biSt, binL[j][st]);
			}
			st = biSt.p;
		}
	}
	if (st == en) {
		if (sw) {
			return {biSt.asc && biSt.downVal <= i, reverse(biSt)};
		} else {
			return {biSt.desc && biSt.upVal <= i, biSt};
		}
	}

	for (int j = binL.size() - 1; j >= 0; j--) {
		if (binL[j][st].p != binL[j][en].p) {
			if (biSt.p == -1) {
				biSt = binL[j][st];
			} else {
				biSt = combine(biSt, binL[j][st]);
			}
			st = biSt.p;
			if (biEn.p == -1) {
				biEn = binL[j][en];
			} else {
				biEn = combine(biEn, binL[j][en]);
			}
			en = biEn.p;
		}
	}
	if (biSt.p == -1) {
		biSt = binL[0][st];
	} else {
		biSt = combine(biSt, binL[0][st]);
	}
	if (biEn.p == -1) {
		biEn = binL[0][en];
	} else {
		biEn = combine(biEn, binL[0][en]);
	}
	if (sw) {
		swap(biEn, biSt);
	}
	auto reVbiEn = reverse(biEn);
	return {biSt.desc && biEn.asc && biSt.upVal < biEn.upVal && biEn.downVal <= i, combine(biSt, reVbiEn)};
}

int dfsSi(int n, int p, vector<bool> &vis, vector<int> &si) {
	if (vis[n]) return 0;
	si[n] = 1;
	for (auto &e: g[n]) {
		if (e.b == p) continue;
		si[n] += dfsSi(e.b, n, vis, si);
	}
	return si[n];
}

int dfsCentro(int n, int p, int to, vector<bool> &vis, vector<int> &si) {
	for (auto &e: g[n]) {
		if (vis[e.b] || e.b == p) continue;
		if (2 * si[e.b] >= to) return dfsCentro(e.b, n, to, vis, si);
	}
	return n;
}

void CenTroDecomp(int n, int p, int d, vector<bool> &vis, vector<int> &si) {
	dfsSi(n, n, vis, si);
	int c = dfsCentro(n, n, si[n], vis, si);
	if (p == -1) p = c;
	pCD[c] = p;
	vis[c] = true;
	dCD[c] = d;
	for (auto &e: g[c]) {
		if (!vis[e.b]) {
			fCD[c].cooC.push_back(e.w);
			CenTroDecomp(e.b, c, d + 1, vis, si);
		}
	}
	std::sort(fCD[c].cooC.begin(), fCD[c].cooC.end());
	fCD[c].a.resize(fCD[c].cooC.size() + 2, 0);
}

void updCD(Ed e) {
	Ed oE = e;
	if (dCD[e.a] < dCD[e.b]) swap(e.a, e.b);
	while (dCD[e.a] != dCD[e.b]) {
		e.a = pCD[e.a];
	}
	while (e.a != e.b) {
		e.a = pCD[e.a];
		e.b = pCD[e.b];
	}
	for (;;) {
		auto [con, bi] = connected(e.w - 1, e.a, oE.a);
		if (con) {
			auto re = connected(e.w, e.a, oE.b);
			con = re.first;
			bi = re.second;
		} else {
			auto re = connected(e.w, e.a, oE.a);
			con = re.first;
			bi = re.second;
		}
		if (con) fCD[e.a].inc(bi.downVal, 1);
		if (pCD[e.a] == e.a) break;
		e.a = pCD[e.a];
	}
}

int numWith(int c, int i) {
	int res = 0;
	int oC = c;
	for (;;) {
		auto [con, bi] = connected(i, oC, c);
		if (con) {
			res += fCD[c].get(1e6) - fCD[c].get(bi.upVal) + 1;
		}
		if (pCD[c] == c) break;
		c = pCD[c];
	}
	return res;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, k;
	cin >> n >> k;
	logT[1] = 0;
	for (int i = 2; i < logT.size(); ++i) {
		logT[i] = logT[i / 2] + 1;
	}
	g = g_t<Ed>(n);
	vector<Que> que(k + n - 1);
	for (int i = 0; i < k + n - 1; ++i) {
		char c;
		cin >> c;
		if (c == 'S') {
			int a, b;
			cin >> a >> b;
			--a;
			--b;
			g[a].push_back({a, b, i});
			g[b].push_back({b, a, i});
			que[i] = {c, a, b, ""};
		}
		if (c == 'Q') {
			int a, b;
			cin >> a >> b;
			--a;
			--b;
			que[i] = {c, a, b, ""};
		}
		if (c == 'C') {
			int a;
			cin >> a;
			--a;
			que[i] = {c, a, -1, ""};
		}
	}
	vector<pair<int, int>> p(n, {0, 0});
	de = vector<int>(n);
	dfs(0, 0, 0, p);
	binLPrep(p);
	vector<bool> vis(n, false);
	vector<int> si(n, 0);
	pCD.resize(n);
	dCD.resize(n);
	fCD.resize(n);
	CenTroDecomp(0, -1, 0, vis, si);
	for (int i = 0; i < que.size(); ++i) {
		if (que[i].c == 'S') {
			updCD({que[i].f, que[i].s, i});
		}
		if (que[i].c == 'Q') {
			que[i].an = (connected(i, que[i].s, que[i].f).first ? "yes" : "no");
		}
		if (que[i].c == 'C') {
			que[i].an = to_string(numWith(que[i].f, i));
		}
	}
	for (auto &qu: que) {
		if (!qu.an.empty()) cout << qu.an << "\n";
	}
}

Compilation message (stderr)

servers.cpp: In member function 'void FenT::inc(int, int)':
servers.cpp:31:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for (int i = p + 1; i < a.size(); i += i & -i) {
      |                       ~~^~~~~~~~~~
servers.cpp: In function 'void binLPrep(std::vector<std::pair<int, int> >&)':
servers.cpp:90: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]
   90 |  for (int i = 0; i < p.size(); ++i) {
      |                  ~~^~~~~~~~~~
servers.cpp:93:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<BinL, std::allocator<BinL> >, std::allocator<std::vector<BinL, std::allocator<BinL> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for (int i = 1; i < binL.size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
servers.cpp:94: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]
   94 |   for (int j = 0; j < p.size(); ++j) {
      |                   ~~^~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:243:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::array<int, 120005>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  243 |  for (int i = 2; i < logT.size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
servers.cpp:284:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Que>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  284 |  for (int i = 0; i < que.size(); ++i) {
      |                  ~~^~~~~~~~~~~~

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 12.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 17.5 / 17.5