Submission #992462

#	Time	Username	Problem	Language	Result	Execution time	Memory
992462		n3rm1n	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2021 ms	12656 KiB

bitaro

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;
const int MAXN = 2e5 + 10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
int n, m, q;
vector < int > g[MAXN];
int dp[MAXN];
int tt, yy;
int marked[MAXN];
void read()
{
    cin >> n >> m >> q;
    int from, to;
    for (int i = 1; i <= m; ++ i)
    {
        cin >> from >> to;
        g[from].push_back(to);
    }

    while(q --)
    {
        cin >> tt >> yy;
        int x;
        memset(marked, 0, sizeof(marked));
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= yy; ++ i)
        {
            cin >> x;
            marked[x] = 1;
        }
        for (int i = 1; i <= n; ++ i)
            dp[i] = -1;
        int maxx = -1, cnt = 0;
        for (int i = tt; i >= 1; -- i)
        {
            if(i == tt)
            { dp[i] = 0;

                if(!marked[i])
                {
                    maxx = 0;

                }
                 //cout << i << " " << dp[i] << " " << maxx << endl;
                continue;
            }
            for (int j = 0; j < g[i].size(); ++ j)
            {
                int nb = g[i][j];
                if(dp[nb] != -1)dp[i] = max(dp[i], dp[nb] + 1);
            }

            if(!marked[i])maxx = max(maxx, dp[i]);
            //cout << i << " " << dp[i] << " " << maxx << endl;
        }
        cout << maxx << endl;
    }
}
int main()
{
    speed();

    read();
    return 0;
}
/***
12 17 1
1 2
2 3
3 4
1 5
2 6
3 7
4 8
5 6
6 7
7 8
5 9
6 10
7 11
8 12
9 10
10 11
11 12
6 3 1 7 12

/*/

Compilation message (stderr)

bitaro.cpp: In function 'void read()':
bitaro.cpp:54:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             for (int j = 0; j < g[i].size(); ++ j)
      |                             ~~^~~~~~~~~~~~~
bitaro.cpp:40:24: warning: unused variable 'cnt' [-Wunused-variable]
   40 |         int maxx = -1, cnt = 0;
      |                        ^~~

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