Submission #336507

#	Time	Username	Problem	Language	Result	Execution time	Memory
336507		amoo_safar	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	933 ms	274796 KiB

bitaro

// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()

using namespace std;

typedef pair<int, int> pii;

const int N = 1e5 + 10;
const int Sqrt = 330;

pii mx[N][Sqrt];
pii tmp[Sqrt];

vector<int> I[N], O[N];

int n, m, Q;

int mk[N], T = 0;
int dp[N];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	for(int i = 0; i < N; i++)
		fill(mx[i], mx[i] + Sqrt, pii(-1, -1));
	cin >> n >> m >> Q;
	int u, v;
	for(int i = 0; i < m; i++){
		cin >> u >> v;
		O[u].pb(v);
		I[v].pb(u);
	}
	for(int i = 1; i <= n; i++){
		mx[i][0] = pii(0, i);
		for(auto adj : I[i]){
			int po = 0, p1 = 0, p2 = 0;
			T ++;
			while(po < Sqrt){
				if(mx[adj][p1].S != -1 && mk[mx[adj][p1].S] == T){
					p1 ++;
					continue;
				}
				if(mx[i][p2].S != -1 && mk[mx[i][p2].S] == T){
					p2 ++;
					continue;
				}

				if(mx[adj][p1].F + 1 > mx[i][p2].F){
					tmp[po ++] = pii(mx[adj][p1].F + (mx[adj][p1].F != -1), mx[adj][p1].S);
					// if(tmp[po - 1].S != -1)
						// cerr << tmp[po - 1].S << '\n';
					p1 ++;
				} else {
					tmp[po ++] = mx[i][p2];
					p2 ++;
				}
				if(tmp[po - 1].S != -1)
					mk[tmp[po - 1].S] = T;
			}
			memcpy(mx[i], tmp, sizeof tmp);
		}
		// cerr << i << " -> ";
		// for(int k = 0; k < Sqrt; k++){
		// 	if(mx[i][k].S != -1)
		// 		cerr << "( " << mx[i][k].F << ' ' << mx[i][k].S << " ), "; 
		// } 
		// cerr << '\n';
	}
	int sz, pl;
	for(int i = 0; i < Q; i++){
		cin >> pl >> sz;
		T ++;
		for(int j = 0; j < sz; j++){
			cin >> u;
			mk[u] = T;
		}
		int ans = -1, fl = 0;
		for(int j = 0; j < Sqrt; j++){
			if(mx[pl][j].S != -1){
				if(mk[mx[pl][j].S] != T){
					ans = mx[pl][j].F;
					break;
				}
			} else {
				fl = 1;
			}
		}
		if(fl){
			cout << "-1\n";
			continue;
		}
		if(ans != -1){
			cout << ans << '\n';
			continue;
		}
		memset(dp, -1, sizeof dp);
		dp[pl] = 0;
		int mxx = -1;
		for(int i = pl; i > 0; i--){
			for(auto adj : O[i])
				if(dp[adj] != -1)
					dp[i] = max(dp[i], dp[adj] + 1);
			if(mk[i] != T)
				mxx = max(mxx, dp[i]);
		}
		cout << mxx << '\n';
	}
	return 0;
}

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