Submission #900575

#	Time	Username	Problem	Language	Result	Execution time	Memory
900575		falaz	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2055 ms	237028 KiB

bitaro

#include <bits/stdc++.h> 
using namespace std;

#define endl '\n'
#define int long long

#define F first 
#define S second

const int N = 1e5 + 3, SQ = 700;
int n, m, q, dis[N];
vector<int> radj[N];
queue<int> qu;
bool mark[N];
vector<pair<int, int>> vec[N];

void bfs() {
	while(qu.size()) {
		int v = qu.front();
		mark[v] = false;
		qu.pop();
		for (auto u : radj[v]) 
			if (dis[v] + 1 > dis[u]) {
				dis[u] = dis[v] + 1;
				if (!mark[u]) {
					qu.push(u);
					mark[u] = true;
				}
			}
	}
}

signed main(){
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m >> q;
	for (int i = 0; i < m; i++) {
		int v, u;
		cin >> v >> u;
		radj[u].push_back(v);
	}
	set<pair<int, int>> st;
	for (int i = 1; i <= n; i++) { 
		if (radj[i].size() == 0)
			vec[i].push_back({i, 0});
		else {
			for (auto v : radj[i]) {
				for (auto u : vec[v]) {
					if (dis[u.F] == 0) {
						dis[u.F] = u.S + 1;
						st.insert({dis[u.F], u.F});
					}
					else if(dis[u.F] < u.S + 1) {
						st.erase({dis[u.F], u.F});
						dis[u.F] = u.S + 1;
						st.insert({dis[u.F], u.F});
					}
					if (st.size() > SQ) {
						int f = st.begin()->S;
						dis[f] = 0;
						st.erase(st.begin());
					}
				}
			}
			while (st.size()) {
				int v = st.begin()->second, f = st.begin()->first;
				st.erase(st.begin());
				vec[i].push_back({v, f});
				dis[v] = 0;
			}
			vec[i].push_back({i, 0});
			sort(vec[i].begin(), vec[i].end());
		}
	}
	while (q--) {
		int t, y;
		cin >> t >> y;
		int c[y + 1];
		c[y] = n + 1;
		for (int i = 0; i < y; i++)
			cin >> c[i];
		if (y <= SQ) {
			int p = 0, ans = -1;
			for (int i = 0; i < int32_t(vec[t].size()); i++) {
				while (c[p] < vec[t][i].F)
					p++;
				if (vec[t][i].F != c[p]) 
					ans = max(vec[t][i].S, ans);
			}
			cout << ans << endl;
		}
		else {
			qu.push(t);
			bfs();
			int p = 0, ans = -1;
			for (int i = 1; i <= t; i++) {
				while (c[p] < i)
					p++;
				if (i != c[p]) 
					ans = max(ans, dis[i]);
				dis[i] = 0;
			}
			cout << ans << endl;
		}
	}	
}

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