Submission #998950

#TimeUsernameProblemLanguageResultExecution timeMemory
998950enviflyBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2013 ms412620 KiB
#pragma GCC optimize("O3, Ofast,unroll-loops")
#include <bits/stdc++.h>
#ifdef UwU
#include "C:\genshin_impact\keqing.cpp"
#else
#define debug(...) 0
#endif
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFLL = 1e18;
 
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define FORE(i,a,b) for(int i = (a); i <= (b); ++i)
#define ROF(i,a,b) for(int i = (a); i >= (b); --i)
#define trav(a,x) for(auto& a: x)
#define sz(x) (int)x.size()
#define make_unique(v) sort(all(v)); v.erase(unique(all(v)), v.end())

template<class T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<class T> bool ckmin(T& a, const T& b){return b<a?a=b,1:0;}
template<class T> bool ckmax(T& a, const T& b){return a<b?a=b,1:0;}
template<int D, typename T>struct vt : public vector<vt<D - 1, T>> { template<typename... Args>
	vt(int n = 0, Args... args) : vector<vt<D - 1, T>>(n, vt<D - 1, T>(args...)) {}};
template<typename T> struct vt<1, T> : public vector<T> {
	vt(int n = 0, const T& val = T()) : vector<T>(n, val) {}};
template<typename T> istream& operator>>(istream& in, vector<T>& a) {for(auto &x : a) in >> x; return in;};
template<typename T> ostream& operator<<(ostream& out, vector<T>& a) {for(auto &x : a) out << x << ' '; return out;};

const int N = 1e5 + 5;

vector<int> rg[N];
int blocked[N];

void solve() {
	int n, m, q; cin >> n >> m >> q;
	FOR(i,0,m){
		int u, v; cin >> u >> v;
		--u; --v;
		rg[v].pb(u);
	}
	int SQ = (int) sqrt(100000);
	vector<vector<pair<int, int>>> path_sizes(n);
	vector<int> from(n, -1);
	FOR(i,0,n){
		path_sizes[i].pb({0, i});
		vector<int> matter;
		trav(j, rg[i]){
			trav(k, path_sizes[j]){
				if(from[k.S] == -1){
					matter.pb(k.S);
					from[k.S] = k.F + 1;
				}
				else{
					ckmax(from[k.S], k.F + 1);
				}
			}
		}
		trav(j, matter){
			path_sizes[i].pb({from[j], j});
		}
		sort(rall(path_sizes[i]));
		// while(sz(path_sizes[i]) > SQ){
			// path_sizes[i].pop_back();
		// }
		if(sz(path_sizes[i]) > SQ){
			path_sizes[i].erase(path_sizes[i].begin() + SQ, path_sizes[i].end());
		}
		trav(j, rg[i]){
			trav(k, path_sizes[j]){
				from[k.S] = -1;
			}
		}
	}
	while(q--){
		int x; cin >> x;
		--x;
		int c; cin >> c;
		vector<int> v(c);
		trav(i, v) cin >> i, --i, blocked[i] = 1;
		
		if(c >= SQ){
			// number of query is limited
			vector<int> dp(x + 1, -INF);
			dp[x] = 0;
			int ans = -1;
			ROF(i,x,0){
				if(dp[i] == -INF) continue;
				if(!blocked[i]) ckmax(ans, dp[i]);
				trav(j, rg[i]){
					ckmax(dp[j], dp[i] + 1);
				}
			}
			cout << ans << "\n";
		}
		else{
			auto& vec = path_sizes[x];
			int ans = -1;
			FOR(i, 0, sz(vec)){
				if(!blocked[vec[i].S]){
					ans = vec[i].F;
					break;
				}
			}
			cout << ans << "\n";	
		}
		
		trav(i, v) blocked[i] = 0;
	}
	
}

signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	int t = 1;
	//cin >> t;
	for(int test = 1; test <= t; test++){
		solve();
	}
}

/*   /\_/\
*   (= ._.)
*   / >  \>
*/

Compilation message (stderr)

bitaro.cpp:128:9: warning: "/*" within comment [-Wcomment]
  128 | /*   /\_/\
      |          
bitaro.cpp:1:46: warning: bad option '-f Ofast' to pragma 'optimize' [-Wpragmas]
    1 | #pragma GCC optimize("O3, Ofast,unroll-loops")
      |                                              ^
bitaro.cpp:27:46: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   27 | template<class T> bool ckmin(T& a, const T& b){return b<a?a=b,1:0;}
      |                                              ^
bitaro.cpp:28:46: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   28 | template<class T> bool ckmax(T& a, const T& b){return a<b?a=b,1:0;}
      |                                              ^
bitaro.cpp:30:28: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   30 |  vt(int n = 0, Args... args) : vector<vt<D - 1, T>>(n, vt<D - 1, T>(args...)) {}};
      |                            ^
bitaro.cpp:32:34: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   32 |  vt(int n = 0, const T& val = T()) : vector<T>(n, val) {}};
      |                                  ^
bitaro.cpp:33:67: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   33 | template<typename T> istream& operator>>(istream& in, vector<T>& a) {for(auto &x : a) in >> x; return in;};
      |                                                                   ^
bitaro.cpp:34:68: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   34 | template<typename T> ostream& operator<<(ostream& out, vector<T>& a) {for(auto &x : a) out << x << ' '; return out;};
      |                                                                    ^
bitaro.cpp:41:12: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   41 | void solve() {
      |            ^
bitaro.cpp:119:13: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
  119 | signed main() {
      |             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...