Submission #408968

#	Time	Username	Problem	Language	Result	Execution time	Memory
408968		kwongweng	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1821 ms	113316 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 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);
	}
	vi used(n, -1);
	FOR(i, 0, n){
	    vii all;
	    all.pb({0, i});
	    for (int u : g[i]){
	        for (ii node : largest[u]){
	            node.F++;
	            all.pb(node);
	        }
	    }
	    sort(all.begin(), all.end());
	    int len = all.size();
	    ROF(j, len-1, 0){
	        if (largest[i].size() > 100) break;
	        if (used[all[j].S] == i) continue;
	        used[all[j].S] = i;
	        largest[i].pb(all[j]);
	    }
	}
	vi invalid(n, -1);
	FOR(j, 0, q){
		int t, y; cin >> t >> y;
		t--;
		FOR(i, 0, y){
		    int c; cin >> c;
		    invalid[c-1] = j;
		}
		if (y > 100){
			vi dp(t+1);
			FOR(i, 0, t+1){
			    if (invalid[i] == j) dp[i] = -1;
				for (int u : g[i]){
					if (dp[u] == -1) continue;
					dp[i] = max(dp[i], dp[u]+1);
				}
			}
			cout << dp[t] << '\n';
		}
		else{
			bool sol = true;
			FOR(i, 0, largest[t].size()){
				if (invalid[largest[t][i].S] != j){
					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: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++)
......
   93 |    FOR(i, 0, largest[t].size()){
      |        ~~~~~~~~~~~~~~~~~~~~~~~         
bitaro.cpp:93:4: note: in expansion of macro 'FOR'
   93 |    FOR(i, 0, largest[t].size()){
      |    ^~~

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