oj.uz

Submission #46350

# Submission time Handle Problem Language Result Execution time Memory
46350 2018-04-19T17:28:14 Z SpaimaCarpatilor Bitaro’s Party (JOI18_bitaro) C++17
0 / 100
 14 ms 6972 KB 
#include<bits/stdc++.h>

using namespace std;

const int K = 200;
int N, M, Q, maxD[100009], ap[100009], h[100009];
vector < int > v[100009], g[100009];
pair < int, int > *dp[100009];

bool cmp (int i, int j) {return (maxD[i] > maxD[j]);}
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d %d", &N, &M, &Q);
while (M --)
{
    int x, y;
    scanf ("%d %d", &x, &y);
    v[y].push_back (x);
    g[x].push_back (y);
}
for (int i=1; i<=N; i++)
{
    dp[i] = new pair < int, int > [K];
    for (int j=0; j<K; j++)
        dp[i][j] = {-3 * N, 0};
}
for (int i=1; i<=N; i++)
{
    int nr = 0;
    for (auto it : v[i])
        for (int j=0; j<K; j++)
            if (dp[it][j].first >= 0)
            {
                int nod = dp[it][j].second;
                if (ap[nod] == 0 || dp[it][j].first + 1 > maxD[nod])
                    maxD[nod] = dp[it][j].first + 1;
                if (ap[nod] == 0)
                    ap[nod] = 1, h[++nr] = nod;
            }
    h[++nr] = i, maxD[i] = 0;
    sort (h + 1, h + nr + 1);
    for (int j=1; j<=nr && j<=K; j++)
        dp[i][j - 1] = {maxD[h[j]], h[j]};
    for (int j=nr + 1; j<=K; j++)
        dp[i][j - 1] = {-1, 0};
    for (int j=1; j<=nr; j++) ap[h[j]] = 0;
}
while (Q --)
{
    int pos, L;
    scanf ("%d %d", &pos, &L);
    for (int i=1; i<=L; i++)
        scanf ("%d", &h[i]), ap[h[i]] = 1;
    int val = -2;
    for (int j=0; j<K; j++)
    {
        if (dp[pos][j].first < 0)
        {
            val = -1;
            break;
        }
        int nod = dp[pos][j].second;
        if (ap[nod] == 0)
        {
            val = dp[pos][j].first;
            break;
        }
    }
    if (val == -2)
    {
        ///that's few times
        maxD[pos] = 0, val = (ap[pos] ? -1 : 0);
        for (int i=pos - 1; i>=1; i--)
        {
            maxD[i] = -3 * N;
            for (auto it : g[i])
                if (it <= pos && maxD[it] + 1 > maxD[i])
                    maxD[i] = maxD[it] + 1;
            if (ap[i] == 0 && maxD[i] > val)
                val = maxD[i];
        }
        printf ("%d\n", val);
        for (int i=1; i<=L; i++)
            ap[h[i]] = 0;
        continue;
    }
    for (int i=1; i<=L; i++)
        ap[h[i]] = 0;
    printf ("%d\n", val);
}
return 0;
}

Compilation message

bitaro.cpp: In function 'int main()':
bitaro.cpp:16:7: 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:20:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &x, &y);
     ~~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:54:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &pos, &L);
     ~~~~~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:56:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d", &h[i]), ap[h[i]] = 1;
         ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5236 KB Output is correct
3 Correct 6 ms 5268 KB Output is correct
4 Correct 5 ms 5268 KB Output is correct
5 Correct 12 ms 6904 KB Output is correct
6 Correct 11 ms 6972 KB Output is correct
7 Correct 13 ms 6972 KB Output is correct
8 Correct 5 ms 6972 KB Output is correct
9 Correct 12 ms 6972 KB Output is correct
10 Correct 14 ms 6972 KB Output is correct
11 Incorrect 14 ms 6972 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5236 KB Output is correct
3 Correct 6 ms 5268 KB Output is correct
4 Correct 5 ms 5268 KB Output is correct
5 Correct 12 ms 6904 KB Output is correct
6 Correct 11 ms 6972 KB Output is correct
7 Correct 13 ms 6972 KB Output is correct
8 Correct 5 ms 6972 KB Output is correct
9 Correct 12 ms 6972 KB Output is correct
10 Correct 14 ms 6972 KB Output is correct
11 Incorrect 14 ms 6972 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5236 KB Output is correct
3 Correct 6 ms 5268 KB Output is correct
4 Correct 5 ms 5268 KB Output is correct
5 Correct 12 ms 6904 KB Output is correct
6 Correct 11 ms 6972 KB Output is correct
7 Correct 13 ms 6972 KB Output is correct
8 Correct 5 ms 6972 KB Output is correct
9 Correct 12 ms 6972 KB Output is correct
10 Correct 14 ms 6972 KB Output is correct
11 Incorrect 14 ms 6972 KB Output isn't correct
12 Halted 0 ms 0 KB -