Submission #383449

#	Time	Username	Problem	Language	Result	Execution time	Memory
383449		thiago4532	Bitaro’s Party (JOI18_bitaro)	C++17	Compilation error	0 ms	0 KiB

bitaro

#include <bits/stdc++.h>
#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];

#define gc getchar_unlocked
inline int scan() {
	int x = gc(), n = 0;
	for(;x < '0' || x > '9'; x = gc()) {}
	for(;x >= '0' && x <= '9'; x = gc()) n = 10*n + x - '0';
	return n;
}

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

		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);
			guarda[i].reserve(sq+1);
		}

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

			for(auto v : grafo[u]) {
				aux.resize(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();
				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 e : guarda[v])
					mark[e.second] = false;
			}
			for (auto& e : guarda[u])
				e.first--;
		}
	}

	for (int i = 1; i <= q; i++) {
		int t, y;
		t = scan(), y= scan();
		vector<int> query(y);
		for (int i = 0; i < y; i++)
			query[i] = scan();
		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:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("unroll-loops")
      | 
bitaro.cpp: In function 'int main()':
bitaro.cpp:50:16: error: 'aux2' was not declared in this scope; did you mean 'aux'?
   50 |     aux.resize(aux2.size() + guarda[v].size());
      |                ^~~~
      |                aux
bitaro.cpp:58: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]
   58 |     for(auto it = aux.begin(); it != aux.end() && guarda[v].size() <= sq; it++)
      |                                                   ~~~~~~~~~~~~~~~~~^~~~~
bitaro.cpp:77:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   77 |     mark[i] = dist[i] = 0;
      |               ~~~~~~~~^~~