oj.uz

Submission #95912

# Submission time Handle Problem Language Result Execution time Memory
95912 2019-02-03T14:58:43 Z toonewbie Bitaro’s Party (JOI18_bitaro) C++17
14 / 100
 1515 ms 325828 KB 
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define _CRT_SECURE_NO_WARNINGS
/****Author: Barish Namazov****/
#include <bits/stdc++.h>

using namespace std;

/***TEMPLATE***/
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

#define F first
#define S second
#define pb push_back

#define endl '\n'

const int max4 = 10004;
const int maxx = 200005;
const int max6 = 1000006;
const int lg5 = 17;

const int INF = 2 * 1000000007;
const long long INFLL = 4LL * 1000000000 * 1000000000;

/***************/

int powmod (int a, int b, int mod) {
    int res = 1; a %= mod;
    for (; b; b >>= 1) {
        if (b & 1) {
            res = 1LL * res * a % mod;
        }
        a = 1LL * a * a % mod;
    }
    return res;
}

int gcd (int a, int b) {
    while (b > 0) {
        int t = a % b;
        a = b, b = t;
    }
    return a;
}

int lcm (int a, int b) {
    return (a / gcd (a, b)) * b;
}

int is_prime (int n) {
    if (n <= 1 || n > 3 && (n % 2 == 0 || n % 3 == 0))
        return 0;
    for (int i = 5, t = 2; i * i <= n; i += t, t = 6 - t)
        if (n % i == 0)
            return 0;
    return 1;
}

/******Don't forget to use long long when needed!!******/

const int Block = 220;

int n, m, q;
vector <int> g[maxx];

vector <pair <int, int>> dp[maxx]; int res[maxx];
inline void update(int u, int v) {
    for (auto i : dp[u]) {
        res[i.S] = i.F;
    }
    for (auto i : dp[v]) {
        res[i.S] = max(res[i.S], i.F + 1);
    }
    for (auto &i : dp[u]) {
        i.F = max(i.F, res[i.S]); res[i.S] = 0;
    }
    vector <pair <int, int>> A, B;
    for (auto i : dp[u]) B.pb(i);
    for (auto i : dp[v]) {
        if (res[i.S] > 0) {
            A.pb({i.F + 1, i.S}); res[i.S] = 0;
        }
    } //sort(rall(A)); sort(rall(B));
    while (!dp[u].empty()) dp[u].pop_back();
    int ptr1 = 0, ptr2 = 0;
    while (ptr1 < A.size() && ptr2 < B.size()) {
        if (A[ptr1] > B[ptr2]) {
            dp[u].pb(A[ptr1++]);
        } else {
            dp[u].pb(B[ptr2++]);
        }
    }
    while (ptr1 < A.size()) dp[u].pb(A[ptr1++]);
    while (ptr2 < B.size()) dp[u].pb(B[ptr2++]);
    while (dp[u].size() > Block) {
        dp[u].pop_back();
    }
}

int has[maxx], lpath[maxx];
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios_base :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> q;
    int a, b;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        g[b].pb(a);
    }
    for (int i = 1; i <= n; i++) {
        for (int j : g[i]) {
            update(i, j);
        }
        if (dp[i].size() < Block) {
            dp[i].pb({0, i});
        }
    }
    vector <int> bad; int tmp;
    int t, y;
    while (q --) {
        cin >> t >> y;
        for (int i = 0; i < y; i++) {
            cin >> tmp;
            bad.pb(tmp); has[tmp] = 1;
        }
        if (y < Block) {
            int res = -1;
            for (auto i : dp[t]) {
                if (has[i.S] == 0) {
                    res = i.F; break;
                }
            }
            cout << res << endl;
        } else {
            for (int i = 1; i <= t; i++) {
                lpath[i] = -has[i];
                for (int j : g[i]) {
                    if (lpath[j] != -1) {
                        lpath[i] = max(lpath[i], lpath[j] + 1);
                    }
                }
            }
            cout << lpath[t] << endl;
        }
        for (int i = 0; i < y; i++) {
            has[bad[i]] = 0;
        }
        bad.clear();
    }
    return 0;
}

Compilation message

bitaro.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
bitaro.cpp: In function 'int is_prime(int)':
bitaro.cpp:55:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     if (n <= 1 || n > 3 && (n % 2 == 0 || n % 3 == 0))
                   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'void update(int, int)':
bitaro.cpp:90:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (ptr1 < A.size() && ptr2 < B.size()) {
            ~~~~~^~~~~~~~~~
bitaro.cpp:90:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (ptr1 < A.size() && ptr2 < B.size()) {
                               ~~~~~^~~~~~~~~~
bitaro.cpp:97:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (ptr1 < A.size()) dp[u].pb(A[ptr1++]);
            ~~~~~^~~~~~~~~~
bitaro.cpp:98:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (ptr2 < B.size()) dp[u].pb(B[ptr2++]);
            ~~~~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9692 KB Output is correct
2 Correct 11 ms 9720 KB Output is correct
3 Correct 11 ms 9720 KB Output is correct
4 Correct 9 ms 9720 KB Output is correct
5 Correct 14 ms 10232 KB Output is correct
6 Correct 13 ms 10232 KB Output is correct
7 Correct 23 ms 10232 KB Output is correct
8 Correct 18 ms 11512 KB Output is correct
9 Correct 18 ms 11640 KB Output is correct
10 Correct 17 ms 11772 KB Output is correct
11 Correct 17 ms 11512 KB Output is correct
12 Correct 17 ms 11000 KB Output is correct
13 Correct 18 ms 11512 KB Output is correct
14 Correct 18 ms 10872 KB Output is correct
15 Correct 15 ms 10616 KB Output is correct
16 Correct 18 ms 10872 KB Output is correct
17 Correct 19 ms 11132 KB Output is correct
18 Correct 15 ms 10744 KB Output is correct
19 Correct 17 ms 11128 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9692 KB Output is correct
2 Correct 11 ms 9720 KB Output is correct
3 Correct 11 ms 9720 KB Output is correct
4 Correct 9 ms 9720 KB Output is correct
5 Correct 14 ms 10232 KB Output is correct
6 Correct 13 ms 10232 KB Output is correct
7 Correct 23 ms 10232 KB Output is correct
8 Correct 18 ms 11512 KB Output is correct
9 Correct 18 ms 11640 KB Output is correct
10 Correct 17 ms 11772 KB Output is correct
11 Correct 17 ms 11512 KB Output is correct
12 Correct 17 ms 11000 KB Output is correct
13 Correct 18 ms 11512 KB Output is correct
14 Correct 18 ms 10872 KB Output is correct
15 Correct 15 ms 10616 KB Output is correct
16 Correct 18 ms 10872 KB Output is correct
17 Correct 19 ms 11132 KB Output is correct
18 Correct 15 ms 10744 KB Output is correct
19 Correct 17 ms 11128 KB Output is correct
20 Correct 517 ms 14112 KB Output is correct
21 Correct 511 ms 14072 KB Output is correct
22 Correct 515 ms 14096 KB Output is correct
23 Correct 538 ms 14148 KB Output is correct
24 Correct 1171 ms 217460 KB Output is correct
25 Correct 1250 ms 225464 KB Output is correct
26 Correct 1359 ms 225372 KB Output is correct
27 Correct 976 ms 218228 KB Output is correct
28 Correct 903 ms 218240 KB Output is correct
29 Correct 924 ms 218024 KB Output is correct
30 Correct 922 ms 217824 KB Output is correct
31 Correct 1326 ms 325828 KB Output is correct
32 Correct 984 ms 217752 KB Output is correct
33 Correct 768 ms 142768 KB Output is correct
34 Correct 965 ms 175396 KB Output is correct
35 Correct 769 ms 142176 KB Output is correct
36 Correct 910 ms 179808 KB Output is correct
37 Correct 1247 ms 249316 KB Output is correct
38 Correct 879 ms 179968 KB Output is correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9692 KB Output is correct
2 Correct 11 ms 9720 KB Output is correct
3 Correct 11 ms 9720 KB Output is correct
4 Correct 9 ms 9720 KB Output is correct
5 Correct 14 ms 10232 KB Output is correct
6 Correct 13 ms 10232 KB Output is correct
7 Correct 23 ms 10232 KB Output is correct
8 Correct 18 ms 11512 KB Output is correct
9 Correct 18 ms 11640 KB Output is correct
10 Correct 17 ms 11772 KB Output is correct
11 Correct 17 ms 11512 KB Output is correct
12 Correct 17 ms 11000 KB Output is correct
13 Correct 18 ms 11512 KB Output is correct
14 Correct 18 ms 10872 KB Output is correct
15 Correct 15 ms 10616 KB Output is correct
16 Correct 18 ms 10872 KB Output is correct
17 Correct 19 ms 11132 KB Output is correct
18 Correct 15 ms 10744 KB Output is correct
19 Correct 17 ms 11128 KB Output is correct
20 Correct 517 ms 14112 KB Output is correct
21 Correct 511 ms 14072 KB Output is correct
22 Correct 515 ms 14096 KB Output is correct
23 Correct 538 ms 14148 KB Output is correct
24 Correct 1171 ms 217460 KB Output is correct
25 Correct 1250 ms 225464 KB Output is correct
26 Correct 1359 ms 225372 KB Output is correct
27 Correct 976 ms 218228 KB Output is correct
28 Correct 903 ms 218240 KB Output is correct
29 Correct 924 ms 218024 KB Output is correct
30 Correct 922 ms 217824 KB Output is correct
31 Correct 1326 ms 325828 KB Output is correct
32 Correct 984 ms 217752 KB Output is correct
33 Correct 768 ms 142768 KB Output is correct
34 Correct 965 ms 175396 KB Output is correct
35 Correct 769 ms 142176 KB Output is correct
36 Correct 910 ms 179808 KB Output is correct
37 Correct 1247 ms 249316 KB Output is correct
38 Correct 879 ms 179968 KB Output is correct
39 Incorrect 1515 ms 221544 KB Output isn't correct
40 Halted 0 ms 0 KB -