Submission #383440

#	Time	Username	Problem	Language	Result	Execution time	Memory
383440		thiago4532	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2098 ms	160512 KiB

bitaro

#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

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], mark2[maxn];
vector<pii> guarda[maxn];

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> m >> q;
	int sq = 190;
	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(aux2.size() + guarda[v].size());
				grau2[v]--;
				if (grau2[v] == 0) fila.push(v);

				merge(aux2.begin(), aux2.end(),
					  guarda[v].begin(), guarda[v].end(), aux.begin(), greater<pii>());

				guarda[v].clear();
				guarda[v].reserve(sq+1);
				for(auto it = aux.begin(); it != aux.end() && 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;
			}
		}
	}

	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) {
			for (int i = 1; i <= n; i++) {
				mark[i] = dist[i] = 0;
				grau2[i] = grau[i];
			}
			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 {
			for (int j = 0; j < y; j++)
				mark2[query[j]] = true;

			int ans = -1;
			for (auto it = guarda[t].begin(); it != guarda[t].end(); it++) {
				if (!mark2[it->second]) {
					ans = it->first;
					break;
				}
			}
		
			for (int j = 0; j < y; j++)
				mark2[query[j]] = false;
			cout << ans << '\n';
		}
	}	
	return 0;
}

Compilation message (stderr)

bitaro.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
bitaro.cpp:4: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      | 
bitaro.cpp: In function 'int main()':
bitaro.cpp:52:68: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |     for(auto it = aux.begin(); it != aux.end() && guarda[v].size() <= sq; it++)
      |                                                   ~~~~~~~~~~~~~~~~~^~~~~
bitaro.cpp:69:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   69 |     mark[i] = dist[i] = 0;
      |               ~~~~~~~~^~~

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