제출 #383445

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
383445		thiago4532	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2039 ms	168456 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];

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> m >> q;
	int sq = 200;
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> 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);
			guarda[i].reserve(sq+1);
		}

		vector<pii> aux;
		aux.reserve(2*sq);
		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]) {
				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 (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;
}

컴파일 시 표준 에러 (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:51: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]
   51 |     for(auto it = aux.begin(); it != aux.end() && guarda[v].size() <= sq; it++)
      |                                                   ~~~~~~~~~~~~~~~~~^~~~~
bitaro.cpp:68:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   68 |     mark[i] = dist[i] = 0;
      |               ~~~~~~~~^~~

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