Submission #384243

#	Time	Username	Problem	Language	Result	Execution time	Memory
384243		JerryLiu06	Bitaro’s Party (JOI18_bitaro)	C++11	100 / 100	1786 ms	414520 KiB

bitaro

#include <bits/stdc++.h>
 
using namespace std;
 
typedef pair<int, int> pii;
 
#define pb push_back
 
#define f first
#define s second
 
int N, M, Q; vector<int> radj[100010];
 
bool mark[100010]; bool busy[100010];
 
int dist[100010];
 
const int BLOCK = 320; const int INF = 1000000000;
 
vector<pii> DP[100010];
 
vector<pii> merge(vector<pii> A, vector<pii> B) {
    vector<pii> res;
 
    int L = 0, R = 0;
 
    while (res.size() < BLOCK) {
        if (L < A.size() && R < B.size()) {
            if (A[L].f > B[R].f) {
                if (!mark[A[L].s]) res.pb(A[L]);
                
                mark[A[L].s] = true; L++;
            }
            else {
                if (!mark[B[R].s]) res.pb(B[R]); 
                
                mark[B[R].s] = true; R++;
            }
        }
        else if (L < A.size()) {
            if (!mark[A[L].s]) res.pb(A[L]); 
            
            mark[A[L].s] = true; L++;
        }
        else if (R < B.size()) {
            if (!mark[B[R].s]) res.pb(B[R]); 
            
            mark[B[R].s] = true; R++;
        }
        else break;
    }
    for (pii P : res) mark[P.s] = false; return res;
}
 
void genDP(int X) {
    DP[X].pb({0, X});
 
    for (int NXT : radj[X]) {
        vector<pii> V = DP[NXT];
 
        for (int i = 0; i < V.size(); i++) V[i].f++;
 
        DP[X] = merge(DP[X], V);
    }
}
int BFS(int X) {
    for (int i = 1; i <= X; i++) dist[i] = -INF;
    
    int res = -1; dist[X] = 0;
    
    for (int i = X; i >= 1; i--) {
        if (!busy[i]) res = max(res, dist[i]);
        
        for (int NXT : radj[i]) dist[NXT] = max(dist[NXT], dist[i] + 1);
    }
    return res;
}

int CHECK(int X) {
    for (pii P : DP[X]) {
        if (!busy[P.s]) return P.f;
    }
    return -1; 
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
 
    cin >> N >> M >> Q;
 
    for (int i = 0; i < M; i++) {
        int A, B; 
 
        cin >> A >> B;
 
        radj[B].pb(A);
    }
    for (int i = 1; i <= N; i++) genDP(i);
    
    for (int i = 0; i < Q; i++) {
        int T, Y;
 
        cin >> T >> Y;
 
        vector<int> V;
        
        for (int i = 0; i < Y; i++) { int X; cin >> X; V.pb(X); busy[X] = true; }
 
        if (Y >= BLOCK) cout << BFS(T) << "\n";
 
        else cout << CHECK(T) << "\n";
 
        for (int i : V) busy[i] = false;
    }
}

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:28:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         if (L < A.size() && R < B.size()) {
      |             ~~^~~~~~~~~~
bitaro.cpp:28: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]
   28 |         if (L < A.size() && R < B.size()) {
      |                             ~~^~~~~~~~~~
bitaro.cpp:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         else if (L < A.size()) {
      |                  ~~^~~~~~~~~~
bitaro.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         else if (R < B.size()) {
      |                  ~~^~~~~~~~~~
bitaro.cpp:52:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   52 |     for (pii P : res) mark[P.s] = false; return res;
      |     ^~~
bitaro.cpp:52:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   52 |     for (pii P : res) mark[P.s] = false; return res;
      |                                          ^~~~~~
bitaro.cpp: In function 'void genDP(int)':
bitaro.cpp:61:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for (int i = 0; i < V.size(); i++) V[i].f++;
      |                         ~~^~~~~~~~~~

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