Submission #466943

#	Time	Username	Problem	Language	Result	Execution time	Memory
466943		maomao90	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1351 ms	415632 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 350

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];
bool used[MAXN];

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) {
		far[i].pb(MP(0, i));
		for (int v : adj[i]) {
			for (auto &[d, u] : far[v]) {
				d++;
			}
			vii cur;
			int l = 0, r = 0;
			while (cur.size() < BLK && 
					(l < far[i].size() || r < far[v].size())) {
				if (r >= far[v].size() || 
						(l < far[i].size() && far[i][l].FI > far[v][r].FI)) {
					if (!used[far[i][l].SE]) {
						used[far[i][l].SE] = 1;
						cur.pb(far[i][l]);
					}
					l++;
				} else {
					if (!used[far[v][r].SE]) {
						used[far[v][r].SE] = 1;
						cur.pb(far[v][r]);
					}
					r++;
				}
			}
			for (auto &[d, u] : far[v]) {
				d--;
			}
			debug(" %d %d\n", i, v);
			for (auto [d, u] : cur) {
				used[u] = 0;
				debug("  %d %d\n", d, u);
			}
			swap(cur, far[i]);
		}
	}
	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) {
			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);
					break;
				}
			}
		}
		printf("%d\n", ans);
		REP (i, 0, y) {
			blk[c[i]] = 0;
		}
	}
	return 0;
}

/*
5 6 3
1 2
2 4
3 4
1 3
3 5
4 5
4 1 1
5 2 2 3
2 3 1 4 5
*/

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:71:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |      (l < far[i].size() || r < far[v].size())) {
      |       ~~^~~~~~~~~~~~~~~
bitaro.cpp:71:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |      (l < far[i].size() || r < far[v].size())) {
      |                            ~~^~~~~~~~~~~~~~~
bitaro.cpp:72:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     if (r >= far[v].size() ||
      |         ~~^~~~~~~~~~~~~~~~
bitaro.cpp:73:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |       (l < far[i].size() && far[i][l].FI > far[v][r].FI)) {
      |        ~~^~~~~~~~~~~~~~~
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++)
......
  122 |    REP (j, 0, far[t].size()) {
      |         ~~~~~~~~~~~~~~~~~~~             
bitaro.cpp:122:4: note: in expansion of macro 'REP'
  122 |    REP (j, 0, far[t].size()) {
      |    ^~~
bitaro.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |  scanf("%d%d%d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:56:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   int s, e; scanf("%d%d", &s, &e);
      |             ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |   scanf("%d%d", &t, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:101:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |    scanf("%d", &c[i]);
      |    ~~~~~^~~~~~~~~~~~~

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