Submission #125912

#	Time	Username	Problem	Language	Result	Execution time	Memory
125912		hugo_pm	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1982 ms	128248 KiB

bitaro

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
 
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= (b); --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)
 
#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second
 
const long long BIG = 1000000000000000000LL;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
 
void solve();
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}
 
const int borne = (int)(1e5) + 5;
const int lowCte = 58;
const int highCte = 60;
 
vector<int> revAdj[borne];
vector<pii> meil[borne];
 
int nbVilles, nbCan, nbReq;
 
int sk[borne];
int vu22[borne]; int tp22 = 0;
int tps = 0;
 
int dp[borne];
 
void solve()
{
	cin >> nbVilles >> nbCan >> nbReq;
	form(i, nbCan) {
		int u, v; cin >> u >> v; --u; --v;
		revAdj[v].push_back(u);
	}
 
	form(i, nbVilles) {
		meil[i].push_back({0, i});
		for (int vo : revAdj[i]) {
			for (auto tr : meil[vo]) {
				meil[i].push_back({tr.fi+1, tr.se});
			}
		}
		vector<pii> ow;
		sort(meil[i].begin(), meil[i].end());
		reverse(meil[i].begin(), meil[i].end());
 
		++tp22;
		for (auto tr : meil[i]) {
			if (vu22[tr.se] == tp22) continue;
			vu22[tr.se] = tp22;
			ow.push_back(tr);
			if ((int)(ow.size()) == highCte) break;
		}
		meil[i] = ow;
	}
 
	form(i, nbReq) {
		int villeArr; cin >> villeArr; --villeArr;
		++tps;
		int nbSkips; cin >> nbSkips;
		form(iRcp, nbSkips) { int x; cin >> x; --x; sk[x] = tps; }
		if (nbSkips < lowCte) {
			bool ff = false;
			for (auto tr : meil[villeArr]) {
				if (sk[tr.se] != tps) {
					cout << tr.fi << "\n";
					ff = true;
					break;
				}
			}
			if (!ff) {
				cout << "-1\n";
			}
		} else {
			form(pos, villeArr+1) {
				dp[pos] = 0;
				for (int vo : revAdj[pos]) if (dp[vo] > 0 || sk[vo] != tps) chmax(dp[pos], dp[vo]+1);
			}
			if (dp[villeArr] == 0 && sk[villeArr] == tps) dp[villeArr] = -1;
			cout << dp[villeArr] << "\n";
		}
	}
}

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