Submission #383453

#	Time	Username	Problem	Language	Result	Execution time	Memory
383453		thiago4532	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2100 ms	165100 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, grau2[maxn];
int dp[maxn];
vector<int> grafo[maxn], g[maxn];
bool mark[maxn], mark2[maxn], tem[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 dfs_dp(int u) {
	if(dp[u] != -1) return dp[u];
	tem[u] = !mark[u];
	int& ans = dp[u];
	ans = 0;
	for(int v : g[u])
		ans = max(ans, dfs_dp(v)+tem[v]), tem[u] |= tem[v];
	return ans;
}

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

		grafo[a].push_back(b);
		g[b].push_back(a);
		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(guarda[u].size() + guarda[v].size());
				grau2[v]--;
				if (grau2[v] == 0) fila.push(v);

				merge(guarda[u].begin(), guarda[u].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) {
			memset(dp, -1, sizeof dp);
			
			for (int i = 0; i < y; i++)
				mark[query[i]] = true;

			cout << (dfs_dp(t)==0&&mark[t]?-1:dp[t]) << '\n';

			for (int i = 0; i < y; i++)
				mark[query[i]] = false;
			
		} 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:69: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]
   69 |     for(auto it = aux.begin(); it != aux.end() && guarda[v].size() <= sq; it++)
      |                                                   ~~~~~~~~~~~~~~~~~^~~~~

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