Submission #1285334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285334		alizhan	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1350 ms	283332 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
const int N = (int)1e6 + 7;
#define skip continue
#define uno first
#define duo second
#define GO while(tt--)
#define ins insert
#define pb push_back
#define all(x) x.begin(), x.end()
#define Kaldun ios::sync_with_stdio(false); cin.tie(nullptr)
#define int long long

int bp(int a, int n) {
	if(n == 0) return 1;
	if(n % 2 == 1) return (bp(a, n-1) * a) % mod;
	long long b = bp(a, n/2);
	return (b * b) % mod;
}
int r,n,m,q;
vector<int>g[N];
int dp[N][3],dis[N],del[N];
vector<pair<int,int>>l[N];
void dfs() {
	for(int u=1; u<=n; u++) {
		vector<int>v;
		v.push_back(u);
		l[u].push_back({0,u});
		dp[u][0] = 0;
		dp[u][1] = u+1;
		for(auto to : g[u]) {
			for(auto x : l[to]) {
				if(dp[x.second][1] != u + 1) {
					v.push_back(x.second);
					dp[x.second][1] = u + 1;
					dp[x.second][0] = x.first + 1;
				}
				else dp[x.second][0] = max(dp[x.second][0], x.first + 1);
			}
		}
		for(int to : v) {
			l[u].push_back({dp[to][0], to});
		}

		sort(l[u].begin(), l[u].end(), greater<pair<int, int>>());

		int len = l[u].size();
		while(len > 100) {
			l[u].pop_back();
			len--;
		}
	}
}
void bfs(int x) {
	fill(dis + 1,dis + n + 1, 0);
	for(int u=1; u<=n; u++) {
		for(int to : g[u]) {
			dis[u] = max(dis[u],dis[to] + 1);
		}
		if(dis[u] == 0 && del[u] == x) {
			dis[u] = -1;
		}
	}
}
int lcm(int a,int b) {
	return (a * b) / __gcd(a,b);
}
void solve() {
	cin>>n>>m>>q;
	for(int i=1; i<=m; i++) {
		int ll,rr;
		cin>>ll>>rr;
		g[rr].push_back(ll);
	}
	if(q>1) dfs();
	for(int i=1; i<=q; i++) {
		int x;
		cin>>r>>x;
		for(int j=1; j<=x; j++) {
			int pop;
			cin>>pop;
			del[pop] = i;
		}
		if(x >= 100 || q==1) {
			bfs(i);
			cout<<dis[r]<<endl;
		}
		else {
			int res = -1;
			for(int j = 0; j < (int)l[r].size(); j++) {
				if(del[l[r][j].second] != i) {
					res = l[r][j].first;
					break;
				}
			}
			cout<<res<<endl;
		}
	}
}
signed main() {
	Kaldun;
	cout.precision(0);
	int tt=1;
	while(tt--) {
		solve();
	}
}

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