Submission #697377

#	Time	Username	Problem	Language	Result	Execution time	Memory
697377		TS_2392	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	1962 ms	388300 KiB

bitaro

#include <bits/stdc++.h>

#define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define SPEED ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define epl emplace
#define pb push_back
#define eb emplace_back

#define EL cout << '\n'
#define dbg(x) cout << #x << " = " << (x) << ' '
#define dbgp(x) cout << #x << " = (" << (x.fi) << ", " << (x.se) << ") "

#define fi first
#define se second
#define mp make_pair

#define sqr(x) (x) * (x)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define lwb lower_bound
#define upb upper_bound
#define ctz __builtin_ctzll
#define pct __builtin_popcountll

using namespace std;

typedef long long ll;
typedef long double ldb;
typedef unsigned int uint;
typedef unsigned long long ull;

typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, int> pii;
typedef pair<ldb, ldb> pld;
typedef pair<double, double> pdd;

template<class T1, class T2> bool minimize(T1 &a, T2 b){return a > b ? a = b, true : false;}
template<class T1, class T2> bool maximize(T1 &a, T2 b){return a < b ? a = b, true : false;}
const int N = 4e5 + 3, Bz = 1002;
int n, m, qsn, d[N], who[N];
bool busy[N], seen[N];
vector<int> adj[N], radj[N];
vector<pii> bestd[N];
vector<pii> mergevector(vector<pii> &v1, vector<pii> &v2){
	vector<pii> V; vector<int> A;
	int p1 = 0, p2 = 0;
	while((p1 < v1.size() || p2 < v2.size()) && V.size() <= Bz){
		int val1 = -100000, val2 = -100000;
		if(p1 < v1.size()) val1 = v1[p1].fi;
		if(p2 < v2.size()) val2 = v2[p2].fi + 1;
		if(val1 > val2){
			V.eb(val1, v1[p1].se);
			seen[v1[p1].se] = 1; A.pb(v1[p1].se);
			p1++;
		}
		else{
			V.eb(val2, v2[p2].se);
			seen[v2[p2].se] = 1; A.pb(v2[p2].se);
			p2++;
		}
		while(p1 < v1.size() && seen[v1[p1].se]) p1++;
		while(p2 < v2.size() && seen[v2[p2].se]) p2++;
	}
	for(int x : A) seen[x]=0;
	return V;
}
int main(){
    SPEED;
    cin >> n >> m >> qsn;
    for(int i = 1; i <= m; ++i){
        int u, v; cin >> u >> v;
        adj[u].eb(v); radj[v].eb(u);
    }
    for(int i = 1; i <= n; ++i){
        bestd[i].eb(0, i);
        for(int &j : radj[i]){
            bestd[i] = mergevector(bestd[i], bestd[j]);
        }
    }
    while(qsn--){
        int city, e;
        cin >> city >> e;
        for(int i = 1; i <= e; ++i){
            cin >> who[i];
            busy[who[i]] = true;
        }
        if(e >= Bz){
            fill(d, d + 1 + city, -1);
            int res = -1; d[city] = 0;
            for(int i = city; i >= 1; --i){
                for(int &j : adj[i]){
                    if(d[j] != -1) maximize(d[i], d[j] + 1);
                }
                if(!busy[i]) maximize(res, d[i]);
            }
            cout << res << '\n';
        }
        else{
            int res = -1;
            for(pii &v : bestd[city]) if(!busy[v.se]){
                maximize(res, v.fi);
                break;
            }
            cout << res << '\n';
        }
        for(int i = 1; i <= e; ++i) busy[who[i]] = false;
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'std::vector<std::pair<int, int> > mergevector(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&)':
bitaro.cpp:51: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]
   51 |  while((p1 < v1.size() || p2 < v2.size()) && V.size() <= Bz){
      |         ~~~^~~~~~~~~~~
bitaro.cpp:51: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]
   51 |  while((p1 < v1.size() || p2 < v2.size()) && V.size() <= Bz){
      |                           ~~~^~~~~~~~~~~
bitaro.cpp:53:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   if(p1 < v1.size()) val1 = v1[p1].fi;
      |      ~~~^~~~~~~~~~~
bitaro.cpp:54:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   if(p2 < v2.size()) val2 = v2[p2].fi + 1;
      |      ~~~^~~~~~~~~~~
bitaro.cpp:65: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]
   65 |   while(p1 < v1.size() && seen[v1[p1].se]) p1++;
      |         ~~~^~~~~~~~~~~
bitaro.cpp:66: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]
   66 |   while(p2 < v2.size() && seen[v2[p2].se]) p2++;
      |         ~~~^~~~~~~~~~~

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