Submission #1275970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275970		lovrot	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	1926 ms	10312 KiB

bitaro

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 2e5 + 10;
const int OO = 2e9;
const int S = 317;

int n, m, q, c[N];
vector<int> g[N], h[N];

int t[N];
vector<int> topo;

void dfs(int u) { 
    t[u] = 1;
    for(auto &v : g[u]) { 
        if(!t[v]) { dfs(v); }
    }
    topo.PB(u);
}

pii tmp[N];
vector<pii> f[N], s;

void merge(int l, int a, int b) { 
    for(int i = 0, j = l, k = l + a; j < l + a || k < l + a + b; ++i) { 
        if(j >= l + a) tmp[i] = s[k++];
        else if(k >= l + a + b) tmp[i] = s[j++];
        else if(s[j] > s[k]) tmp[i] = s[j++];
        else tmp[i] = s[k++];
    }

    for(int i = 0; i < a + b; ++i) { s[l + i] = tmp[i]; }
}

int dnc(const int &u, int lo, int hi) { 
    if(lo >= hi) { return 0; }
    if(lo + 1 == hi) { 
        for(const auto &i : f[h[u][lo]]) { s.PB({i.X + 1, i.Y}); }
        return f[h[u][lo]].size();
    }

    int mi = (lo + hi) / 2, l = s.size(), a = dnc(u, lo, mi), b = dnc(u, mi, hi);
    merge(l, a, b);
    return a + b;
}

int main() { 
    scanf("%d%d%d", &n, &m, &q);
    for(; m--; ) { 
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].PB(v);
        h[v].PB(u);
    }

    for(int i = 1; i <= n; ++i) { if(!t[i]) { dfs(i); } }
    reverse(topo.begin(), topo.end());

    memset(t, 0, sizeof(t));
    for(const auto &i : topo) { 
        s.clear();
        dnc(i, 0, h[i].size()); 
        s.PB({0, i});

        for(const auto &j : s) {
            if(!t[j.Y]) { 
                f[i].PB(j);
                t[j.Y] = 1;
            }

            if(f[i].size() > S) { break; }
        }

        for(const auto &j : f[i]) { t[j.Y] = 0; }
//        printf("%d\n", i);
//        for(const auto &j : f[i]) { printf("%d %d, ", j.X, j.Y); }
//        printf("\n");
    }

    for(; q--; ) { 
        int u, k;
        scanf("%d%d", &u, &k);
        for(int i = 0; i < k; ++i) { 
            scanf("%d", c + i);
            t[c[i]] = -OO; 
        }

        bool flag = 0;

        if(k > S) { 
            for(const auto &i : topo) { 
                for(const auto &j : h[i]) { t[i] = max(t[i], t[j] + 1); }
            }

            if(t[u] >= 0) { 
                flag = 1;
                printf("%d", t[u]);
            }

            for(int i = 1; i <= n; ++i) t[i] = 0;
        } else { 
            for(const auto &i : f[u]) { 
                if(t[i.Y] != -OO) { 
                    flag = 1;
                    printf("%d\n", i.X);
                    break;
                }
            }
            for(int i = 0; i < k; ++i) t[c[i]] = 0;
        }

        if(!flag) { printf("-1\n"); }
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     scanf("%d%d%d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         scanf("%d%d", &u, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:96:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |             scanf("%d", c + i);
      |             ~~~~~^~~~~~~~~~~~~

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