Submission #479791

#	Time	Username	Problem	Language	Result	Execution time	Memory
479791		MilosMilutinovic	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1880 ms	420704 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const int N = 100005;
const int M = 333;

int n, m, q;
int dp[N];
int sz[N];
vector<pii> dist[N];
vector<int> g[N], rg[N];
bool blk[N];
int lst[N];
int cost[N];

int main()
{
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 0; i < m; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		--u; --v;
		g[u].pb(v);
		rg[v].pb(u);
	}
	for (int i = 0; i < n; i++) lst[i] = -1, cost[i] = 0;
	for (int i = 0; i < n; i++) {
		vector<int> curr;
		for (int j : rg[i]) {
			for (auto he : dist[j]) {
				int st = he.fi, D = he.se;
				if (lst[st] != i) {
					cost[st] = D + 1;
					curr.pb(st);
					lst[st] = i;
				} else {
					cost[st] = max(cost[st], D + 1);
				}
			}
			if (lst[j] != i) {
				lst[j] = i;
				cost[j] = 1;
				curr.pb(j);
			}
		}
		curr.pb(i);
		sort(curr.begin(), curr.end(), [&](int i, int j) {
			return cost[i] > cost[j];
		});
		for (int j = 0; j < min((int) curr.size(), M); j++) {
			dist[i].pb({curr[j], cost[curr[j]]});
		}
	}
	while (q--) {
		int S, qSz;
		scanf("%d%d", &S, &qSz);
		--S;
		vector<int> curr;
		for (int i = 0; i < qSz; i++) {
			int qId;
			scanf("%d", &qId);
			--qId;
			curr.push_back(qId);
			blk[qId] = true;
		}
		if (qSz >= M) {
			for (int i = 0; i < n; i++) {
				if (blk[i]) dp[i] = -1;
				else dp[i] = 0;
				for (int j : rg[i]) {
					if (dp[j] != -1) {
						dp[i] = max(dp[i], dp[j] + 1);
					}
				}
			}
			printf("%d\n", dp[S]);
		} else {
			int ans = -1;
			for (auto my : dist[S]) {
				if (!blk[my.fi]) {
					ans = max(ans, my.se);
				}
			}
			printf("%d\n", ans);
		}
		for (int u : curr) blk[u] = false;
	}
	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |  scanf("%d%d%d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   scanf("%d%d", &S, &qSz);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
bitaro.cpp:79:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |    scanf("%d", &qId);
      |    ~~~~~^~~~~~~~~~~~

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