Submission #743717

#	Time	Username	Problem	Language	Result	Execution time	Memory
743717		m_abv	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2070 ms	20392 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 mpp make_pair
#define sz(x) (int)x.size()
//#define int ll

const int N = 1e5+10, X = 317; 
int n, m, q;
set<pii> st[N];
int dp[N];
vi g[N];

void caldp() {
	for(int i = 1; i <= n; i++) {
		map<int, int> mp;
		for(int j : g[i]) {
			for(auto it = st[j].begin(); it != st[j].end(); it++) {
				pii e = *it;
				int x = e.s, w = e.f+1;
				if(w > mp[x]) {
					st[i].erase(mpp(mp[x], x));
					mp[x] = w;
					st[i].insert(mpp(mp[x], x));
				}
				while(sz(st[i]) > X)
					st[i].erase(st[i].begin());
			}
			if(1 > mp[j]) {
				st[i].erase(mpp(mp[j], j));
				mp[j] = 1;
				st[i].insert(mpp(mp[j], j));
			}
			while(sz(st[i]) > X)
				st[i].erase(st[i].begin());
		}
	}
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m >> q;
	for(int i = 0; i < m; i++) {
		int v, u;
		cin >> v >> u;
		g[u].pb(v);
	}
	caldp();
	while(q--) {
		int t, y;
		cin >> t >> y;
		if(y < X) {
			set<int> hld;
			for(int i = 0; i < y; i++) {
				int x; cin >> x;
				hld.insert(x);
			}
			int flag = 0;
			for(auto it = st[t].rbegin(); !flag && it != st[t].rend(); it++) {
				pii e = *it;
				if(!hld.count(e.s))
					flag = e.f;
			}
			if(!flag) {
				if(hld.count(t))
					cout << -1 << endl;
				else
					cout << 0 << endl;
			}
			else
				cout << flag << endl;
		}
		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: 0 / 7
• Subtask 3: 0 / 86