Submission #384231

#	Time	Username	Problem	Language	Result	Execution time	Memory
384231		JerryLiu06	Bitaro’s Party (JOI18_bitaro)	C++11	7 / 100	2106 ms	413928 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;

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) {
    memset(dist, -1, sizeof dist);
    
    queue<int> Q; Q.push(X); dist[X] = 0;

    int res = -1;

    while (!Q.empty()) {
        int CUR = Q.front(); Q.pop();

        if (!busy[CUR]) res = max(res, dist[CUR]);

        for (int NXT : radj[CUR]) {
            if (dist[NXT] < dist[CUR] + 1) Q.push(NXT), dist[NXT] = dist[CUR] + 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: 0 / 7
• Subtask 3: 0 / 86