Submission #408960

#	Time	Username	Problem	Language	Result	Execution time	Memory
408960		kwongweng	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	1119 ms	112896 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);
	}
	
	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();
	    int pos = max(len-101, 0);
	    ROF(j, len-1, pos){
	        largest[i].pb(all[j]);
	    }
	}
	
	while (q--){
		int t, y; cin >> t >> y;
		t--;
		if (y > 100){
			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: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++)
......
   82 |     FOR(j, 0, g[i].size()){
      |         ~~~~~~~~~~~~~~~~~              
bitaro.cpp:82:5: note: in expansion of macro 'FOR'
   82 |     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++)
......
   98 |    FOR(i, 0, largest[t].size()){
      |        ~~~~~~~~~~~~~~~~~~~~~~~         
bitaro.cpp:98:4: note: in expansion of macro 'FOR'
   98 |    FOR(i, 0, largest[t].size()){
      |    ^~~

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