Submission #69574

#	Time	Username	Problem	Language	Result	Execution time	Memory
69574		chpipis	Bitaro’s Party (JOI18_bitaro)	C++11	14 / 100	1584 ms	295340 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)

// START for segment tree
#define params int p, int L, int R
#define housekeep int mid = (L + R) >> 1, left = p << 1, right = left | 1
// END

#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
    advance(it, -n);
    return it;
}

template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
    advance(it, n);
    return it;
}
#endif

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

template<typename T>
inline T sq(T a) { return a * a; }

//#ifdef LOCAL_MACHINE
//#endif

const int INF = 1e9;
const int MAXN = 1e5 + 5;
const int SIZE = 350;

const ii senti(-1, 0);

struct myds {
    ii ar[SIZE];
    myds() {
        fill(ar, ar + SIZE, senti);
    }

    void merge(const myds &rhs) {
        myds res;
        int x = 0, y = 0, pos = 0;
        while (pos < SIZE) {
            ii elem(senti);
            if (x >= SIZE) {
                if (y >= SIZE)
                    break;
                elem = rhs.ar[y];
            } else if (y >= SIZE) {
                elem = ar[x];
            } else {
                elem = max(ar[x], rhs.ar[y]);
            }
            while (x < SIZE && ar[x] == elem)
                x++;
            while (y < SIZE && rhs.ar[y] == elem)
                y++;
            res.ar[pos++] = elem;
        }
        (*this) = res;
    }
} paths[MAXN];
vi gr[MAXN], rgr[MAXN];
vi bl[MAXN], quer[MAXN];
int dp[MAXN];
int ans[MAXN];
bool exist[MAXN];

int main() {
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    int n, m, q;
    scanf("%d %d %d", &n, &m, &q);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        gr[u].pb(v);
        rgr[v].pb(u);
    }
    vii heavy;
    for (int i = 1; i <= q; i++) {
        int t, y;
        scanf("%d %d", &t, &y);
        ans[i] = -1;
        bl[i].resize(y);
        for (int j = 0; j < y; j++)
            scanf("%d", &bl[i][j]);
        if (y < SIZE - 1)
            quer[t].pb(i);
        else
            heavy.pb(mp(t, i));
    }
    for (int i = 1; i <= n; i++) {
        paths[i].ar[0] = mp(-1, i);
        for (auto v : rgr[i]) {
            paths[i].merge(paths[v]);
        }
        for (int j = 0; j < SIZE; j++) {
            if (paths[i].ar[j].se != 0)
                paths[i].ar[j].fi++;
        }
        for (auto it : quer[i]) {
            for (auto el : bl[it])
                exist[el] = true;
            int res = -1;
            for (int j = 0; j < SIZE; j++) {
                if (!exist[paths[i].ar[j].se]) {
                    res = paths[i].ar[j].fi;
                    break;
                }
            }
            for (auto el : bl[it])
                exist[el] = false;
            ans[it] = res;
        }
    }
    for (auto it : heavy) {
        for (auto el : bl[it.se])
            exist[el] = true;
        int t = it.fi;
        fill(dp, dp + MAXN, -INF);
        int mx = -1;
        dp[t] = 0;
        for (int u = t; u >= 1; u--) {
            for (auto v : gr[u])
                dp[u] = max(dp[u], dp[v] + 1);
            if (!exist[u] && dp[u] > mx)
                mx = dp[u];
        }
        ans[it.se] = mx;
        for (auto el : bl[it.se])
            exist[el] = false;
    }
    for (int i = 1; i <= q; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:102:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:112:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &t, &y);
         ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:116:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &bl[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~

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