Submission #125511

#	Time	Username	Problem	Language	Result	Execution time	Memory
125511		hugo_pm	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2063 ms	388460 KiB

bitaro

#include <bits/stdc++.h>
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 = 340;
const int highCte = 350;

vector<int> revAdj[borne];
vector<pii> meil[borne];

int nbVilles, nbCan, nbReq;

int sk[borne];
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});
			}
		}
		sort(meil[i].begin(), meil[i].end());
		reverse(meil[i].begin(), meil[i].end());
		int da = max(0, (int)(meil[i].size()) - highCte);
		form(ii, da) meil[i].pop_back();
	}

	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: 0 / 7
• Subtask 3: 0 / 86