Submission #1100578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100578		anhphant	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1717 ms	524288 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first 
#define se second
#define dot cerr << "passed " << '\n';
#define debug(x) cerr << "debug : " << #x << " = " << x << '\n';

ll N, M, Q;
vector<ll> GR[100007], invGR[100007];
vector<pair<ll, ll>> vlist[100007];
ll added[100007];
struct query {
	ll t, y;
	vector<ll> c;
};
query Queries[100007];
const ll Bsz = ceil(sqrt(100000));
ll DP[100007], deleted[100007];

int main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0); cerr.tie(0);
	if (fopen("FILE.INP", "r")) {
		freopen("FILE.INP", "r", stdin);
		freopen("FILE.OUT", "w", stdout);
	}

	cin >> N >> M >> Q;
	for(int i = 1, u, v; i <= M; ++i) {
		cin >> u >> v;
		GR[u].push_back(v);
		invGR[v].push_back(u);
	}
	for(int i = 1; i <= Q; ++i) {
		cin >> Queries[i].t >> Queries[i].y;
		for(int j = 1, c; j <= Queries[i].y; ++j) {
			cin >> c;
			Queries[i].c.push_back(c);
		}
	}

	//dot;

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

	// dot;

	for(int u = 1; u <= N; ++u) {
		// debug(u);
		for(int v : GR[u]) {
			// debug(u);
			// debug(v);
			// debug(vlist[u].size());
			// debug(vlist[v].size());
			vector<pair<ll, ll>> tmp;
			ll pl = 0, pr = 0;
			while(pl < vlist[u].size() || pr < vlist[v].size()) {
				// cerr << "in looop : " << pl << " " << pr << '\n';
				if (pl < vlist[u].size() && vlist[u][pl].se + 1 > vlist[v][pr].se) {
					if (!added[vlist[u][pl].fi]) {
						tmp.push_back({vlist[u][pl].fi, vlist[u][pl].se + 1});
						added[vlist[u][pl].fi] = 1;
					}
					pl++;
				}
				else {
					if (!added[vlist[v][pr].fi]) {
						tmp.push_back(vlist[v][pr]);
						added[vlist[v][pr].fi] = 1;
					}
					pr++;
				}

				if (tmp.size() == Bsz) break;
			}
			// dot;
			vlist[v] = tmp;
			// cerr << "vlist check " << v << '\n';
			for(auto [x, y] : tmp) {
				// cerr << "{" <<  x << "," << y << "}" << "; ";
				added[x] = 0;
			}
			// cerr << '\n';
		}
	}

	// dot;
	fill(DP, DP + 1 + N + 3, -1e18);

	for(int i = 1; i <= Q; ++i) {
		// debug(i);
		auto [t, y, c] = Queries[i];
		if (y >= Bsz) {
			DP[t] = 0;
			for(int u = t; u >= 1; --u) {
				if (DP[u] == -1e18) continue;
				for(int v : invGR[u]) {
					DP[v] = max(DP[v], DP[u] + 1);
					// cerr << "edge : " << u << " " << v << " " << DP[u] << " " << DP[v] << '\n';
				}
			}
			for(int u : c) deleted[u] = 1;
			ll ans = -1;
			for(int u = 1; u <= t; ++u) {
				if (deleted[u]) continue;
				ans = max(ans, DP[u]);
				// cerr << u << " : " << DP[u] << '\n';
			}
			cout << (ans == -1? -1 : ans) << '\n';
			for(int u : c) deleted[u] = 0;
			for(int u = t; u >= 1; --u) {
				DP[u] = -1e18;
			}
		}
		else {
			for(int u : c) deleted[u] = 1;
			ll ans = -1;
			for(auto [x, y] : vlist[t]) {
				if (deleted[x]) continue;
				ans = y;
				break;
			}
			cout << (ans == -1? -1 : ans) << '\n';
			for(int u : c) deleted[u] = 0;
		}
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:60:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |    while(pl < vlist[u].size() || pr < vlist[v].size()) {
      |          ~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:60:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |    while(pl < vlist[u].size() || pr < vlist[v].size()) {
      |                                  ~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:62:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     if (pl < vlist[u].size() && vlist[u][pl].se + 1 > vlist[v][pr].se) {
      |         ~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:82:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |    for(auto [x, y] : tmp) {
      |             ^
bitaro.cpp:95:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |   auto [t, y, c] = Queries[i];
      |        ^
bitaro.cpp:121:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  121 |    for(auto [x, y] : vlist[t]) {
      |             ^
bitaro.cpp:25:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   freopen("FILE.INP", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:26:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |   freopen("FILE.OUT", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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