Submission #383425

#	Time	Username	Problem	Language	Result	Execution time	Memory
383425		thiago4532	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	4 ms	5868 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
int n, m, q, dist[maxn], grau[maxn], grau2[maxn];
vector<int> grafo[maxn];
bool mark[maxn];
vector<pii> guarda[maxn];

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> m >> q;
	int sq = sqrt(n);
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		if (a > b) swap(a, b);

		grafo[a].push_back(b);
		grau[b]++;
		grau2[b]++;
	}

	{ // precompute unordered map
		queue<int> fila;
		for (int i = 1; i <= n; i++) {
			guarda[i].push_back({0, i});
			if (grau2[i] == 0) fila.push(i);
		}

		while (!fila.empty()) {
			int u = fila.front();
			fila.pop();
			vector<pii> aux2(guarda[u]);
			for(auto& e : aux2)
				e.first++;

			for(auto v : grafo[u]) {
				vector<pii> aux;
				grau2[v]--;
				if (grau2[v] == 0) fila.push(v);

				merge(aux2.begin(), aux2.end(),
					  guarda[v].begin(), guarda[v].end(), back_inserter(aux));
				guarda[v].clear();

				for(auto it = aux.rbegin(); it != aux.rend() && guarda[v].size() <= sq; it++)
					if(!mark[it->second]) guarda[v].push_back(*it), mark[it->second] = true;

				for (auto const& e : guarda[v])
					mark[e.second] = false;
				reverse(guarda[v].begin(), guarda[v].end());
			}
		}

		for (int u = 1; u <= n; u++){
			for (auto v : guarda[u]) {
				cout << u << " " << v.first << " " << v.second << "\n";
			}
		}
	}

	for (int i = 1; i <= q; i++) {
		

		int t, y;
		cin >> t >> y;
		vector<int> query(y);
		for (int i = 0; i < y; i++)
			cin >> query[i];
		if (y <= sq) {
			memset(mark, 0, sizeof mark);
			memset(dist, 0, sizeof dist);
			memcpy(grau2, grau, sizeof grau);
			for (int i = 0; i < y; i++)
				mark[query[i]] = true;

			queue<int> fila;
			for (int i = 1; i <= n; i++)
				if (grau2[i] == 0) fila.push(i);

			while (!fila.empty()) {
				int u = fila.front();
				fila.pop();

				for(auto v : grafo[u]) {
					grau2[v]--;
					if (grau2[v] == 0) fila.push(v);

					if (dist[u] > 0 || !mark[u])
						dist[v] = max(dist[v], dist[u] + 1);
				}
			}
			if (dist[t] == 0 && mark[t]) cout << "-1\n";
			else cout << dist[t] << '\n';
		} else {
			unordered_set<int> gg;
			for (int i = 0; i < y; i++)
				gg.insert(query[i]);

			int ans = -1;
			for (auto it = guarda[t].rbegin(); it != guarda[t].rend(); it++) {
				if (gg.find(it->second) == gg.end()) {
					ans = it->first;
					break;
				}
			}
			cout << ans << '\n';
		}
	}	
	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:48:70: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |     for(auto it = aux.rbegin(); it != aux.rend() && guarda[v].size() <= sq; it++)
      |                                                     ~~~~~~~~~~~~~~~~~^~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86