Submission #924195

#	Time	Username	Problem	Language	Result	Execution time	Memory
924195		42kangaroo	Inside information (BOI21_servers)	C++17	50 / 100	234 ms	66644 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;
};

array<int, 120005> logT;
g_t<BinL> binL;
g_t<Ed> g;
vector<int> de;

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

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

bool connected(int i, int st, int en) {
	if (st == en) return true;
	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;
		} else {
			return biSt.desc && biSt.upVal <= i;
		}
	}

	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);
	}
	return biSt.desc && biEn.asc && biSt.upVal < biEn.upVal && biEn.downVal <= i;
}

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);
	for (int i = 0; i < que.size(); ++i) {
		if (que[i].c == 'Q') {
			que[i].an = (connected(i, que[i].s, que[i].f) ? "yes" : "no");
		}
	}
	for (int i = 0; i < que.size(); ++i) {
		if (que[i].an != "") cout << que[i].an << "\n";
	}
}

Compilation message (stderr)

servers.cpp: In function 'void binLPrep(std::vector<std::pair<int, int> >&)':
servers.cpp:55: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]
   55 |  for (int i = 0; i < p.size(); ++i) {
      |                  ~~^~~~~~~~~~
servers.cpp:58: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]
   58 |  for (int i = 1; i < binL.size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
servers.cpp:59: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]
   59 |   for (int j = 0; j < p.size(); ++j) {
      |                   ~~^~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:131:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::array<int, 120005>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |  for (int i = 2; i < logT.size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
servers.cpp:166:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Que>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |  for (int i = 0; i < que.size(); ++i) {
      |                  ~~^~~~~~~~~~~~
servers.cpp:171:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Que>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |  for (int i = 0; i < que.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