Submission #466777

#	Time	Username	Problem	Language	Result	Execution time	Memory
466777		maomao90	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2104 ms	120752 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 105

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 visited[MAXN];
vi topo;
void gettopo(int u) {
	for (int v : adj[u]) {
		if (visited[v]) continue;
		visited[v] = 1;
		gettopo(v);
	}
	topo.pb(u);
}

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) {
		vii all;
		vi vs;
		for (int v : adj[i]) {
			for (auto [d, j] : far[v]) {
				if (mxd[j] == -1) {
					vs.pb(j);
				}
				mxto(mxd[j], d + 1);
			}
		}
		for (int v : vs) {
			all.pb(MP(mxd[v], v));
		}
		all.pb(MP(0, i));
		sort(ALL(all), greater<ii>());
		REP (j, 0, min(BLK, (int) all.size())) {
			far[i].pb(all[j]);
		}
		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) {
			topo.clear();
			REP (i, 1, n + 1) {
				visited[i] = 0;
				dist[i] = -1;
			}
			visited[t] = 1;
			gettopo(t);
			dist[t] = 0;
			RREP (i, topo.size() - 1, 0) {
				debug(" %d\n", topo[i]);
				for (int v : adj[topo[i]]) {
					mxto(dist[v], dist[topo[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]) {
					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: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++)
......
  123 |    REP (j, 0, far[t].size()) {
      |         ~~~~~~~~~~~~~~~~~~~             
bitaro.cpp:123:4: note: in expansion of macro 'REP'
  123 |    REP (j, 0, far[t].size()) {
      |    ^~~
bitaro.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |  scanf("%d%d%d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:66:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |   int s, e; scanf("%d%d", &s, &e);
      |             ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |   scanf("%d%d", &t, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:98:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |    scanf("%d", &c[i]);
      |    ~~~~~^~~~~~~~~~~~~

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