Submission #466952

#	Time	Username	Problem	Language	Result	Execution time	Memory
466952		maomao90	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1595 ms	215760 KiB

bitaro

#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifdef DEBUG
#define debug(args...) _debug(args)
void _debug(const char* format, ...) {
	va_list args;
	va_start(args, format);
	vprintf(format, args);
	va_end(args);
}
#else
#define debug(args...)
#endif

#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 200005
#define BLK 210

int n, m, q;
vi adj[MAXN];
vii far[MAXN];
int mxd[MAXN];
int t, y;
int c[MAXN];
bool blk[MAXN];
int dist[MAXN];

vi vs;
bool isPos(int x) {
	int cnt = 0;
	for (int i : vs) {
		cnt += mxd[i] >= x;
	}
	return cnt <= BLK;
}

int main() {
	scanf("%d%d%d", &n, &m, &q);
	REP (i, 0, m) {
		int s, e; scanf("%d%d", &s, &e);
		adj[e].pb(s);
	}
	REP (i, 1, n + 1) {
		mxd[i] = -1;
	}
	REP (i, 1, n + 1) {
		vs.clear();
		for (int v : adj[i]) {
			for (auto [d, j] : far[v]) {
				if (mxd[j] == -1) {
					vs.pb(j);
				}
				mxto(mxd[j], d + 1);
			}
		}
		vs.pb(i);
		mxd[i] = 0;
		int lo = 0, hi = n, mid;
		// minimum number where there are <= BLK stuff with mxd >= mid
		while (lo < hi) {
			mid = lo + hi >> 1;
			if (isPos(mid)) {
				hi = mid;
			} else {
				lo = mid + 1;
			}
		}
		vi ex;
		for (int v : vs) {
			if (mxd[v] >= hi) {
				far[i].pb(MP(mxd[v], v));
			} else if (mxd[v] == hi - 1) {
				ex.pb(v);
			}
		}
		while (far[i].size() < BLK && !ex.empty()) {
			int v = ex.back(); ex.pop_back();
			far[i].pb(MP(mxd[v], v));
		}
		for (int v : vs) {
			mxd[v] = -1;
		}
	}
	while (q--) {
		scanf("%d%d", &t, &y);
		REP (i, 0, y) {
			scanf("%d", &c[i]);
			blk[c[i]] = 1;
		}
		int ans = -1;
		if (y >= BLK - 5) {
			REP (i, 1, n + 1) {
				dist[i] = -1;
			}
			dist[t] = 0;
			RREP (i, t, 1) {
				if (dist[i] == -1) continue;
				for (int v : adj[i]) {
					mxto(dist[v], dist[i] + 1);
					debug("  %d: %d\n", v, dist[v]);
				}
			}
			REP (i, 1, t + 1) {
				if (dist[i] == -1 || blk[i]) continue;
				mxto(ans, dist[i]);
			}
		} else {
			REP (j, 0, far[t].size()) {
				if (!blk[far[t][j].SE]) {
					mxto(ans, far[t][j].FI);
				}
			}
		}
		printf("%d\n", ans);
		REP (i, 0, y) {
			blk[c[i]] = 0;
		}
	}
	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:85:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |    mid = lo + hi >> 1;
      |          ~~~^~~~
bitaro.cpp:8:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
  132 |    REP (j, 0, far[t].size()) {
      |         ~~~~~~~~~~~~~~~~~~~             
bitaro.cpp:132:4: note: in expansion of macro 'REP'
  132 |    REP (j, 0, far[t].size()) {
      |    ^~~
bitaro.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  scanf("%d%d%d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:64:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   int s, e; scanf("%d%d", &s, &e);
      |             ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |   scanf("%d%d", &t, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:111:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |    scanf("%d", &c[i]);
      |    ~~~~~^~~~~~~~~~~~~

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