Submission #43979

#	Time	Username	Problem	Language	Result	Execution time	Memory
43979		MatheusLealV	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2093 ms	215948 KiB

bitaro

#include <bits/stdc++.h>
#define N 100050
#define RAIZ 350
#define f first
#define s second
#define gc getchar_unlocked
using namespace std;
typedef pair<int, int> pii;

int n, m, q, dp[N], block[N], grau[N], save[N], qualquer[N], aparecidos[N];

vector<int> grafo[N], lista;

vector < pii > best[N];

inline void solve()
{
	for(int i = 1; i <= n; i++) if(!grau[i]) lista.push_back(i);

	for(int i = 0; i < lista.size(); i++)
	{
		int x = lista[i];

		vector<pii> aux2;

		for(auto tt: best[x]) aux2.push_back({tt.f - 1, tt.s });

		for(auto v: grafo[x])
		{
			grau[v] --;

			vector<pii> aux ( best[v].size() + best[x].size() ), fim;

			vector<int> cu;

			merge( best[v].begin(), best[v].end(), aux2.begin(), aux2.end(), aux.begin() );

			for(int i = 0; i < aux.size(); i++)
			{
				if(aparecidos[aux[i].s]) continue;

				fim.push_back(aux[i]);

				cu.push_back(aux[i].s);

				aparecidos[aux[i].s] = 1;
			}

			for(auto tt: cu) aparecidos[tt] = 0;

			while(fim.size() > 400) fim.pop_back();

			best[v] = fim;

			if(!grau[v]) lista.push_back(v);
		}
	}
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>m>>q;

	for(int i = 1, a, b; i <= m; i++)
	{
		cin>>a>>b;

		grafo[a].push_back(b);

		grau[b] ++;

		save[b] ++;
	}

	for(int i = 1; i <= n; i++) best[i].push_back({0, i});

	solve();

	for(int t = 1; t <= q; t++)
	{
		int T, Y;

		cin>>T>>Y;

		vector<int> mudar;

		if(Y > RAIZ)
		{
			memset(dp, -1, sizeof dp);

			memset(qualquer, 0, sizeof qualquer);

			for(int i = 1; i <= n; i++) grau[i] = save[i];

			for(int i = 1, x; i <= Y; i++)
			{
				cin>>x;

				block[x] = 1;

				mudar.push_back(x);
			}

			vector<pii> lista;

			for(int i = 1; i <= n; i++)
			{
				if(!grau[i]) dp[i] = 0, lista.push_back( {i, !block[i] } );

				qualquer[i] = !block[i];

				if(!block[i]) dp[i] = 0;

				else dp[i] = -1;
			}

			for(int i = 0; i < lista.size(); i++)
			{
				int x = lista[i].f, b = lista[i].s;

				for(auto v: grafo[x])
				{
					grau[v] --;

					if(b && dp[x] != -1) dp[v] = max(dp[v], dp[x] + 1);

					qualquer[v] = (qualquer[v] || b);

					if(!grau[v]) lista.push_back({v, qualquer[v]});
				}
			}

			cout<<dp[T]<<"\n";

			for(auto tt: mudar) block[tt] = 0;

			continue;
		}

		for(int i = 1, x; i <= Y; i++)
		{
			cin>>x;

			block[x] = 1;

			mudar.push_back(x);
		}

		int ans = -1;

		for(int i = 0; i < best[T].size(); i++)
		{
			int d = -best[T][i].f, v = best[T][i].s;

			if(!block[v]) ans = max(ans, d);
		}

		for(auto tt: mudar) block[tt] = 0;

		cout<<ans<<"\n";
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'void solve()':
bitaro.cpp:20:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < lista.size(); i++)
                 ~~^~~~~~~~~~~~~~
bitaro.cpp:38:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < aux.size(); i++)
                   ~~^~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:119:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < lista.size(); i++)
                   ~~^~~~~~~~~~~~~~
bitaro.cpp:153:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < best[T].size(); i++)
                  ~~^~~~~~~~~~~~~~~~

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