Submission #624939

#	Time	Username	Problem	Language	Result	Execution time	Memory
624939		Arnch	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1336 ms	182780 KiB

bitaro

// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
#define endl '\n'

constexpr ll inf = 1e18, N = 1e5 + 10, SQ = 200;

int n, m, q, ans_t[N];
int t[N], y[N], pos[N], d[N];
pair<int, int> dp[N][SQ];
bool mark[N], ex[N];
vector<int> adj[N], radj[N], vc[N], topol;

void dfs(int x) {
	mark[x] = 1;
	for(auto j : adj[x]) {
		if(mark[j]) continue;
		dfs(j);
	}
	topol.push_back(x);
}

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);

	cin >>n >>m >>q;
	for(int i = 0; i < m; i++) {
		int u, v; cin >>u >>v;
		adj[u].push_back(v);
		radj[v].push_back(u);
	}

	for(int i = 1; i <= n; i++) {
		if(!mark[i]) dfs(i);
	}
	reverse(All(topol));

	for(int i = 0; i < Sz(topol); i++) {
		pos[topol[i]] = i;
	}

	for(int i = 0; i < q; i++) {
		cin >>t[i] >>y[i];
		if(y[i] >= SQ) {
			vector<int> his;
			for(int j = 0; j < y[i]; j++) {
				int u; cin >>u;
				his.push_back(u);
				ex[u] = 1;
			}

			int ind = pos[t[i]], ans = -1;
			memset(d, -1, sizeof(d));
			d[t[i]] = 0;
			for(int j = ind; j >= 0; j--) {
				for(auto x : adj[topol[j]]) {
					if(d[x] == -1) continue;
					d[topol[j]] = max(d[x] + 1, d[topol[j]]);
				}
				if(!ex[topol[j]]) ans = max(ans, d[topol[j]]);
			}

			for(auto j : his) {
				ex[j] = 0;
			}
			his.clear();

			ans_t[i] = ans;
			continue;
		}
		for(int j = 0; j < y[i]; j++) {
			int u; cin >>u;
			vc[i].push_back(u);
		}
	}


	memset(dp, -1, sizeof(dp));

	for(auto u : topol) {
		int ptr = 0;
		priority_queue<pair<pair<int, int>, pair<int, int> > > pq;
		for(auto v : radj[u]) {
			pq.push({dp[v][0], {0, v}});
		}
		memset(mark, 0, sizeof(mark));
		while(!pq.empty() && ptr < SQ) {
			int v = pq.top().second.second, ptrv = pq.top().second.first; pair<int, int> val = pq.top().first; pq.pop();
			if(val.first == -1) break;
			if(!mark[val.second])
				dp[u][ptr++] = {val.first + 1, val.second};
			mark[val.second] = 1;
			pq.push({dp[v][++ptrv], {ptrv, v}});
		}
		if(ptr < SQ) dp[u][ptr] = {0, u};
	}

	/*cout<<"------------" <<endl;
	for(auto j : topol) cout<<j <<' ';
	cout<<endl;
*/

//	cout<<dp[4][1].first <<" " <<dp[4][1].second <<endl;


	for(int i = 0; i < q; i++) {
		if(y[i] >= SQ) cout<<ans_t[i] <<endl;
		else {
			bool f = 0;
			for(auto j : vc[i]) {
				ex[j] = 1;
			}
			for(int j = 0; j < SQ; j++) {
				if(!ex[dp[t[i]][j].second]) {
					cout<<dp[t[i]][j].first <<endl;
					f = 1;
					break;
				}
			}
			if(!f) {
				cout<<-1 <<endl;
			}
			for(auto j : vc[i]) {
				ex[j] = 0;
			}
		}
	}
		

    return 0;
}

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