Submission #1271791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271791		cmiuc	Bitaro’s Party (JOI18_bitaro)	C++20	14 / 100	554 ms	423600 KiB

bitaro

#include <iostream>
#include <vector>

using namespace std;
const int N = 1e5 + 10, K = 320;
vector<int> nei[N], rnei[N], ord;
vector<pair<int,int>> vec[N], nw;
int seen[N], busy[N], Max[N];

void dfs(int u){
	seen[u] = 1;
	for (int i : nei[u]){
		if (seen[i] == 0)
			dfs(i);
	}
	ord.push_back(u);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, m, q, a, b;
	cin>>n>>m>>q;

	for (int i=1;i<=m;i++){
		cin>>a>>b;
		nei[a].push_back(b);
		rnei[b].push_back(a);
	}

	for (int i=1;i<=n;i++){
		if (seen[i] == 0)
			dfs(i);
	}

	for (int i=n-1;i>=0;i--){
		int u = ord[i];
		vec[u] = {{0, u}};
		for (int j : rnei[u]){
			nw.clear();
			int id1 = 0, id2 = 0;
			while (id1 < vec[u].size() or id2 < vec[j].size()){
				if (nw.size() == K)
					break;
				if (id1 < vec[u].size() and id2 < vec[j].size() and vec[u][id1].second == vec[j][id2].second)
					nw.push_back({max(vec[u][id1].first, vec[j][id2].first + 1), vec[j][id2].second}), id1++, id2++;
				else if (id1 < vec[u].size() and (id2 == vec[j].size() or vec[j][id2].first + 1 <= vec[u][id1].first))
					nw.push_back(vec[u][id1]), id1++;
				else if (id2 < vec[j].size())
					nw.push_back({vec[j][id2].first + 1, vec[j][id2].second}), id2++;
			}
			swap(vec[u], nw);
		}
	}

	for (int i=1;i<=q;i++){
		int t, sz, c, ans = -1;
		cin>>t>>sz;
		for (int j=1;j<=sz;j++)
			cin>>c, busy[c] = i;

		if (sz < K){
			for (int j=0;j<vec[t].size();j++)
				if (busy[vec[t][j].second] != i)
					ans = max(ans, vec[t][j].first);
		}
		else{
			for (int j=1;j<=n;j++)
				Max[j] = -1e9;
			Max[t] = 0;
			for (int j : ord){
				for (int v : nei[j])
					Max[j] = max(Max[j], Max[v] + 1);
			}
			for (int j=1;j<=n;j++){
				if (busy[j] != i)
					ans = max(ans, Max[j]);
			}
		}
		cout<<ans<<'\n';
	}
}

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