Submission #408699

#	Time	Username	Problem	Language	Result	Execution time	Memory
408699		kwongweng	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	3 ms	540 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define F first
#define S second
ll MOD = 1000000007;
ll INF = 1000000000;
 
ll power(ll base, ll n){
	if (n == 0) return 1;
	if (n == 1) return base;
	ll halfn = power(base, n/2);
	if (n % 2 == 0) return (halfn * halfn) % MOD;
	return (((halfn * halfn) % MOD) * base) % MOD;
}
 
ll inverse(ll n){
	return power(n, MOD-2);
}
 
ll add(ll a, ll b){
	return (a+b) % MOD;
}
 
ll mul(ll a, ll b){
	return (a*b) % MOD;
}
 
ll gcd(ll a, ll b){
	if (a == 0) return b;
	if (a == 1) return 1;
	return gcd(b%a, a);
}

int B = 100;

int main(){
    ios::sync_with_stdio(false);
    int n, m, q; cin >> n >> m >> q;
    vi g[n];
    vii largest[n];
    FOR(i, 0, m){
    	int s, e; cin >> s >> e;
    	g[e-1].pb(s-1);
	}
	FOR(i, 0, n){
		int sz = g[i].size();
		vi cnt(sz);
		int num = 0;
		FOR(j, 0, sz){
			if (largest[g[i][j]].size() > cnt[j]){
				num++;
			}
		}
		set<int> st;
		while (num > 0 && largest[i].size() <= 100){
			int u = largest[g[i][0]][cnt[0]].S; 
			int maxi = largest[g[i][0]][cnt[0]].F;
			int index = 0;
			FOR(j, 1, sz){
				int v = g[i][j];
				if (largest[v][cnt[j]].F > maxi){
					u = largest[v][cnt[j]].S;
					maxi = largest[v][cnt[j]].F;
					index = j;
				}
			}
			if (st.find(u) == st.end()){
				st.insert(u);
				largest[i].pb({maxi+1, u});
			}
			cnt[index]++;
			if (cnt[index] == largest[g[i][index]].size()) num--;
		}
		if (largest[i].size() <= 100){
			largest[i].pb({0, i});
		}		
	}
	while (q--){
		int t, y; cin >> t >> y;
		t--;
		if (y > 100){
			//do bfs
			vi dp(t+1);
			FOR(i, 0, y){
				int c; cin >> c; c--;
				if (c > t) continue;
				dp[c] = -1; 
			}
			FOR(i, 0, t+1){
				FOR(j, 0, g[i].size()){
					int u = g[i][j];
					if (dp[u] == -1) continue;
					dp[i] = max(dp[i], dp[u]+1);
				}
			}
			cout << dp[t] << '\n';
		}else{
			set<int> st;
			FOR(i, 0, y){
				int c; cin >> c;
				c--;
				st.insert(c);
			}
			bool sol = true;
			FOR(i, 0, largest[t].size()){
				if (st.find(largest[t][i].S) == st.end()){
					cout << largest[t][i].F << '\n';
					sol = false; break;
				}
			}
			if (sol) cout << -1 << '\n';
		}
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:60:32: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   60 |    if (largest[g[i][j]].size() > cnt[j]){
bitaro.cpp:82:19: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |    if (cnt[index] == largest[g[i][index]].size()) num--;
bitaro.cpp:9:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
  100 |     FOR(j, 0, g[i].size()){
      |         ~~~~~~~~~~~~~~~~~              
bitaro.cpp:100:5: note: in expansion of macro 'FOR'
  100 |     FOR(j, 0, g[i].size()){
      |     ^~~
bitaro.cpp:9:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
  115 |    FOR(i, 0, largest[t].size()){
      |        ~~~~~~~~~~~~~~~~~~~~~~~         
bitaro.cpp:115:4: note: in expansion of macro 'FOR'
  115 |    FOR(i, 0, largest[t].size()){
      |    ^~~

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