Submission #744292

#	Time	Username	Problem	Language	Result	Execution time	Memory
744292		m_abv	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	727 ms	260628 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define f first
#define s second
#define pb push_back
#define pf push_front
#define mp make_pair
#define sz(x) (int)x.size()
//#define int ll

const int N = 1e5+10, X = 320, INF = 1e9; 
int n, m, q;
pii tp[N][X], hld[X];
int dp[N], ban[X];
vi g[N];
bool use[N];

void caltp() {
	for(int i = 1; i <= n; i++) {
		tp[i][0] = mp(0, i);
		for(int j : g[i]) {
			int it = 0,
				l = 0,
				r = 0,
				d, c;
			while(it < X) {
				if((l>=X || tp[i][l].f<0) && (r>=X || tp[j][r].f<0))
					break;
				if((r>=X || tp[j][r].f<0) || ((l<X) && tp[i][l].f >= tp[j][r].f+1)) {
					d = tp[i][l].f;
					c = tp[i][l++].s;
				}
				else {
					d = tp[j][r].f+1;
					c = tp[j][r++].s;
				}
				if(!use[c]) {
					hld[it++] = mp(d, c);
					use[c] = 1;
				}
			}
			for(int k = 0; k < it; k++) {
				tp[i][k] = hld[k];
				use[hld[k].s] = 0;
			}
		}
	}
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m >> q;
	for(int i = 1; i <= n; i++)
		for(int j = 0; j < X; j++)
			tp[i][j] = mp(-INF, -INF);
	for(int i = 0; i < m; i++) {
		int v, u;
		cin >> v >> u;
		g[u].pb(v);
	}
	caltp();
	while(q--) {
		int t, y;
		cin >> t >> y;
		if(y < X) {
			for(int i = 0; i < y; i++) {
				cin >> ban[i];
				use[ban[i]] = 1;
			}
			int flag = -1;
			for(int i = 0; i < X && (flag==-1); i++) {
				if(tp[t][i].f < 0)
					break;
				if(!use[tp[t][i].s]) {
					flag = tp[t][i].f;
					break;
				}
			}
			cout << flag << endl;
			for(int i = 0; i < y; i++)
				use[ban[i]] = 0;
		}
		else {
			memset(dp, 0, sizeof dp);
			for(int i = 0; i < y; i++) {
				int x; cin >> x;
				dp[x] = -1;
			}
			for(int i = 1; i <= t; i++)
				for(int j :g[i])
					if(dp[j] != -1)
						dp[i] = max(dp[i], dp[j]+1);
			cout << dp[t] << endl;
		}
	}
}

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