Submission #347320

#	Time	Username	Problem	Language	Result	Execution time	Memory
347320		parsabahrami	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1808 ms	187800 KiB

bitaro

// Call my Name and Save me from The Dark
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 1e5 + 1, SQ = 105;
int n, m, q, R[N], dp[N], M[N];
vector<int> adj[N]; vector<pii> far[N]; vector<pair<int, vector<int>>> sml[N]; vector<pair<pii, vector<int>>> big;

int main() {
    memset(R, -1, sizeof R);
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= m; i++) {
        int u, v; scanf("%d%d", &u, &v);
        adj[u].push_back(v);
    }
    for (int i = 1; i <= q; i++) {
        int t, v; scanf("%d%d", &v, &t);
        vector<int> vec;
        for (; t; t--) {
            int u; scanf("%d", &u);
            vec.push_back(u);
        }
        if (SZ(vec) >= SQ) big.push_back({{i, v}, vec});
        else sml[v].push_back({i, vec});
    }
    for (auto[x, vec] : big) {
        int v = x.S, id = x.F;
        fill(dp, dp + N, 0);
        for (int u : vec) dp[u] = -1;
        for (int i = 1; i <= v; i++) {
            for (int u : adj[i]) {
                if (~dp[i]) dp[u] = max(dp[u], dp[i] + 1);
            }
        }
        R[id] = dp[v];
    }
    for (int v = 1; v <= n; v++) {
        for (int u : adj[v]) {
            far[u].push_back({1, v});    
        }
        sort(far[v].begin(), far[v].end(), greater<pii>());
    }
    for (int v = 1; v <= n; v++) {
        vector<pii> tmp;
        for (pii e : far[v]) tmp.push_back({e.F + 1, e.S});
        for (int u : adj[v]) {
            vector<pii> kir = far[u];
            far[u] = {};
            merge(kir.begin(), kir.end(), tmp.begin(), tmp.end(), back_inserter(far[u]), greater<pii>());
            kir = far[u]; far[u] = {};
            for (pii x : kir) {
                if (!M[x.S]) far[u].push_back(x), M[x.S] = 1;
            }
            for (pii x : far[u]) M[x.S] = 0;
            far[u].resize(unique(far[u].begin(), far[u].end()) - far[u].begin());
            while (SZ(far[u]) > SQ) far[u].pop_back();
        }
        far[v].push_back({0, v});
        for (auto[id, vec] : sml[v]) {
            for (int u : vec) M[u] = 1;
            for (pii x : far[v]) {
                if (!M[x.S]) {
                    R[id] = x.F;
                    break;
                }
            }
            for (int u : vec) M[u] = 0;
        } 
    }
    for (int i = 1; i <= q; i++) printf("%d\n", R[i]);
    return 0;
}

Compilation message (stderr)

bitaro.cpp:2: warning: ignoring #pragma comment  [-Wunknown-pragmas]
    2 | #pragma comment(linker, "/stack:200000000")
      | 
bitaro.cpp: In function 'int main()':
bitaro.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   21 |     scanf("%d%d%d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:23:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |         int u, v; scanf("%d%d", &u, &v);
      |                   ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:27:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |         int t, v; scanf("%d%d", &v, &t);
      |                   ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:30:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |             int u; scanf("%d", &u);
      |                    ~~~~~^~~~~~~~~~

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