Submission #739655

#	Time	Username	Problem	Language	Result	Execution time	Memory
739655		Markomafko972	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1171 ms	218280 KiB

bitaro

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
using namespace std;

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int OFF = (1 << 20);

int n, m, q, a, b, tren, kol;
vector<int> v[100005];
int sq = 233;
int bio[100005];
int z[100005];
int dp[100005];
vector<pii> w[100005];
int pos[100005];

int dfs(int x) {
	if (dp[x] != -1) return dp[x];
	
	dp[x] = -1e9;
	if (bio[x] == 0) dp[x] = 0;
	for (int i = 0; i < (int)v[x].size(); i++) {
		dp[x] = max(dp[x], dfs(v[x][i])+1);
	}
	
	return dp[x];
}

void natrag(int x) {
	if (dp[x] == -1) return;
	
	dp[x] = -1;
	for (int i = 0; i < (int)v[x].size(); i++) natrag(v[x][i]);
}

int main () {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m >> q;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		v[b].push_back(a);
	}
	
	for (int i = 1; i <= n; i++) {
		
		//cout << i << endl;
		
		while ((int)w[i].size() < sq) {
			int da = 0;
			for (int j = 0; j < (int)v[i].size(); j++) {
				while (pos[v[i][j]] < (int)w[v[i][j]].size() && bio[w[v[i][j]][pos[v[i][j]]].X]) pos[v[i][j]]++;
				
				if (pos[v[i][j]] < (int)w[v[i][j]].size()) {
					da = 1;
				}
			}
			if (da == 0) break;
			
			int maxi = 0, cvor = 0, slj = 0;
			for (int j = 0; j < (int)v[i].size(); j++) {
				if (pos[v[i][j]] < (int)w[v[i][j]].size() && w[v[i][j]][pos[v[i][j]]].Y+1 > maxi && bio[w[v[i][j]][pos[v[i][j]]].X] == 0) {
					maxi = w[v[i][j]][pos[v[i][j]]].Y+1;
					cvor = w[v[i][j]][pos[v[i][j]]].X;
					slj = v[i][j];
				}
			}
			
			w[i].push_back({cvor, maxi});
			pos[slj]++;
			bio[cvor] = 1;
			//cout << cvor << " " << maxi << endl;
		}
		
		if ((int)w[i].size() < sq) w[i].push_back({i, 0});
		
		for (int j = 0; j < (int)v[i].size(); j++) pos[v[i][j]] = 0;
		for (int j = 0; j < (int)w[i].size(); j++) bio[w[i][j].X] = 0;
	}
	
	
	//for (int i = 0; i < w[6].size(); i++) cout << w[6][i].X << " " << w[6][i].Y << endl;
	//cout << endl;
	
	for (int i = 0; i < q; i++) {
		cin >> tren >> kol;
		for (int j = 0; j < kol; j++) {
			cin >> z[j];
			bio[z[j]] = 1;
		}
		
		if (kol >= sq) {
			memset(dp, -1, sizeof dp);
			int rj = dfs(tren);
			if (rj < 0) cout << "-1\n";
			else cout << rj << "\n";
			//natrag(tren);
		}
		else {
			int da = 0;
			for (int j = 0; j < (int)w[tren].size(); j++) {
				if (bio[w[tren][j].X] == 0) {
					cout << w[tren][j].Y << "\n";
					da = 1;
					break;
				}
			}
			
			if (da == 0) cout << "-1\n";
		}
		
		for (int j = 0; j < kol; j++) bio[z[j]] = 0;
	}

	return 0;
}

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