Submission #722106

#	Time	Username	Problem	Language	Result	Execution time	Memory
722106		NothingXD	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1076 ms	114328 KiB

bitaro

/*

   Wei Wai Wei Wai
   Zumigat nan damu dimi kwayt rayt

*/

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
/*typedef __uint128_t L;
  struct FastMod {
  ull b, m;
  FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
  ull reduce(ull a) {
  ull q = (ull)((L(m) * a) >> 64);
  ull r = a - q * b; // can be proven that 0 <= r < 2*b
  return r >= b ? r - b : r;
  }
  };
  FastMod FM(2);
  */
void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e5 + 10;
const int sq = 100;
const int inf = 1e9;

int n, m, q, a[maxn], dp[maxn];
vector<int> g[maxn];
vector<pii> val[maxn];
bool mark[maxn];

vector<pii> merge(vector<pii> a, vector<pii> b){
	vector<pii> res;
	int pta = 0, ptb = 0;
	while(pta < a.size() || ptb < b.size()){
		if (ptb == b.size() || (pta < a.size() && a[pta] > b[ptb])){
			res.push_back(a[pta]);
			pta++;
		}
		else{
			res.push_back(b[ptb]);
			ptb++;
		}
	}
	return res;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

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

	for (int i = 1; i <= n; i++){
		val[i].push_back({-1, i});
		for (int j = sq; val[i].size() < sq; j--) if (j != i) val[i].push_back({-inf, j});
		for (auto u: g[i]){
			vector<pii> tmp = merge(val[i], val[u]);
			val[i].clear();
			for (auto x: tmp){
				if (val[i].size() == sq) break;
				if (!mark[x.S]) val[i].push_back(x);
				mark[x.S] = true;
			}
			for (auto x: val[i]) mark[x.S] = false;
		}
		for (int j = 0; j < sq; j++){
			val[i][j].F++;
		}
	}

	while(q--){
		int v, k; cin >> v >> k;
		for (int i = 1; i <= k; i++){
			cin >> a[i];
			mark[a[i]] = true;
		}
		if (k < sq){
			for (auto [x, y]: val[v]){
				if (!mark[y]){
					cout << (x < 0? -1: x) << '\n';
					break;
				}
			}
		}
		else{
			for (int i = 1; i <= v; i++){
				dp[i] = (mark[i]? -inf: 0);
				for (auto u: g[i]){
					dp[i] = max(dp[i], dp[u] + 1);
				}
			}
			cout << (dp[v] < 0? -1: dp[v]) << '\n';
		}
		for (int i = 1; i <= k; i++) mark[a[i]] = false;
	}

	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'std::vector<std::pair<int, int> > merge(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
bitaro.cpp:57:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  while(pta < a.size() || ptb < b.size()){
      |        ~~~~^~~~~~~~~~
bitaro.cpp:57:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  while(pta < a.size() || ptb < b.size()){
      |                          ~~~~^~~~~~~~~~
bitaro.cpp:58:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   if (ptb == b.size() || (pta < a.size() && a[pta] > b[ptb])){
      |       ~~~~^~~~~~~~~~~
bitaro.cpp:58:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   if (ptb == b.size() || (pta < a.size() && a[pta] > b[ptb])){
      |                           ~~~~^~~~~~~~~~

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