Submission #383459

#	Time	Username	Problem	Language	Result	Execution time	Memory
383459		thiago4532	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1871 ms	181996 KiB

bitaro

#define _FORTIFY_SOURCE 0 
#pragma GCC optimize("Ofast") 
#pragma GCC optimize("no-stack-protector") 
#pragma GCC optimize("unroll-loops") 
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx") 
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx") 
#pragma GCC optimize("inline") 
#pragma GCC optimize("-fgcse") 
#pragma GCC optimize("-fgcse-lm") 
#pragma GCC optimize("-fipa-sra") 
#pragma GCC optimize("-ftree-pre") 
#pragma GCC optimize("-ftree-vrp") 
#pragma GCC optimize("-fpeephole2") 
#pragma GCC optimize("-ffast-math") 
#pragma GCC optimize("-fsched-spec") 
#pragma GCC optimize("unroll-loops") 
#pragma GCC optimize("-falign-jumps") 
#pragma GCC optimize("-falign-loops") 
#pragma GCC optimize("-falign-labels") 
#pragma GCC optimize("-fdevirtualize") 
#pragma GCC optimize("-fcaller-saves") 
#pragma GCC optimize("-fcrossjumping") 
#pragma GCC optimize("-fthread-jumps") 
#pragma GCC optimize("-funroll-loops") 
#pragma GCC optimize("-fwhole-program") 
#pragma GCC optimize("-freorder-blocks") 
#pragma GCC optimize("-fschedule-insns") 
#pragma GCC optimize("inline-functions") 
#pragma GCC optimize("-ftree-tail-merge") 
#pragma GCC optimize("-fschedule-insns2") 
#pragma GCC optimize("-fstrict-aliasing") 
#pragma GCC optimize("-fstrict-overflow") 
#pragma GCC optimize("-falign-functions") 
#pragma GCC optimize("-fcse-skip-blocks") 
#pragma GCC optimize("-fcse-follow-jumps") 
#pragma GCC optimize("-fsched-interblock") 
#pragma GCC optimize("-fpartial-inlining") 
#pragma GCC optimize("no-stack-protector") 
#pragma GCC optimize("-freorder-functions") 
#pragma GCC optimize("-findirect-inlining") 
#pragma GCC optimize("-fhoist-adjacent-loads") 
#pragma GCC optimize("-frerun-cse-after-loop") 
#pragma GCC optimize("inline-small-functions") 
#pragma GCC optimize("-finline-small-functions") 
#pragma GCC optimize("-ftree-switch-conversion") 
#pragma GCC optimize("-foptimize-sibling-calls") 
#pragma GCC optimize("-fexpensive-optimizations") 
#pragma GCC optimize("-funsafe-loop-optimizations") 
#pragma GCC optimize("inline-functions-called-once") 
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
constexpr 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 = 200;
	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:1: warning: "_FORTIFY_SOURCE" redefined
    1 | #define _FORTIFY_SOURCE 0
      | 
<built-in>: note: this is the location of the previous definition
bitaro.cpp:25:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
   25 | #pragma GCC optimize("-fwhole-program")
      |                                       ^
bitaro.cpp:32:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize("-fstrict-overflow")
      |                                         ^
bitaro.cpp:34:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
   34 | #pragma GCC optimize("-fcse-skip-blocks")
      |                                         ^
bitaro.cpp:48:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
   48 | #pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                   ^
bitaro.cpp:63:17: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   63 | inline int scan() {
      |                 ^
bitaro.cpp:63:17: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
bitaro.cpp:63:17: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
bitaro.cpp:63:17: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
bitaro.cpp:70:17: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   70 | int dfs_dp(int u) {
      |                 ^
bitaro.cpp:70:17: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
bitaro.cpp:70:17: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
bitaro.cpp:70:17: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
bitaro.cpp:80:10: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   80 | int main() {
      |          ^
bitaro.cpp:80:10: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
bitaro.cpp:80:10: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
bitaro.cpp:80:10: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
bitaro.cpp: In function 'int main()':
bitaro.cpp:118: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]
  118 |     for(auto it = aux.begin(); it != aux.end() && guarda[v].size() <= sq; it++)
      |                                                   ~~~~~~~~~~~~~~~~~^~~~~

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