Submission #357784

#	Time	Username	Problem	Language	Result	Execution time	Memory
357784		AriaH	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1914 ms	159852 KiB

bitaro

/** Im the best because i work as hard as i possibly can **/
 
///#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include <bits/stdc++.h>
using namespace std;
 
typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define endl                        "\n"
 
const int N = 1e5 + 5;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;
const int B = 190;
 
ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }
 
vector < int  > G[N];
 
int n, m, q, mark[N], A[N], use[N], dp[N];
 
pii dis[B][N], cu[B];
 
void merge(int v, int u)
{
    for(int i = 0; i < B; i ++) cu[i] = Mp(-1e9, 0);
    int l = 0, r = 0, i = 0;
    for(i = 0; i < B; i ++)
    {
	while(l < B and mark[dis[l][v].S]) l ++;
	while(r < B and mark[dis[r][u].S]) r ++;
	if(r >= B  and l >= B) break;
	if(r >= B or dis[l][v].F + 1 > dis[r][u].F)
	{
	    cu[i] = dis[l][v], cu[i].F ++;
	    mark[cu[i].S] = 1;
	}
	else
	{
	    cu[i] = dis[r][u];
	    mark[cu[i].S] = 1;
	}
    }
    for(i = 0; i < B; i ++) mark[cu[i].S] = 0, dis[i][u] = cu[i];
}
 
int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1; i <= m; i ++)
    {
	int a, b, x, y;
	scanf("%d%d", &a, &b);
	x = min(a, b), y = max(a, b);
	G[x].push_back(y);
    }
    for(int i = 1; i <= n; i ++)
    {
	dis[0][i] = Mp(0, i);
	for(int j = 1; j < B; j ++)
	{
	    dis[j][i] = Mp(-1e9, 0);
	}
    }
    for(int i = 1; i <= n; i ++)
    {
	for(auto u : G[i]) merge(i, u);
    }
    while(q--)
    {
	int v, cnt;
	scanf("%d%d", &v, &cnt);
	for(int i = 1; i <= cnt; i ++)
	{
	    scanf("%d", &A[i]);
	    use[A[i]] = 1;
	}
	if(cnt >= B)
	{
	    for(int i = 0; i <= v; i ++) dp[i] = -1e9;
	    for(int i = 1; i <= v; i ++)
	    {
		if(!use[i])
		{
		    dp[i] = max(dp[i], 0);
		}
		for(auto u : G[i]) dp[u] = max(dp[u], dp[i] + 1);
	    }
	    printf("%d\n", max(dp[v], -1));
	}
	else
	{
	    for(int i = 0; i < B; i ++)
	    {
		if(!use[dis[i][v].S])
		{
		    printf("%d\n", max(dis[i][v].F, -1));
		    break;
		}
	    }
	}
	for(int i = 1; i <= cnt; i ++) { use[A[i]] = 0; }
    }
    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:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |  scanf("%d%d", &a, &b);
      |  ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |  scanf("%d%d", &v, &cnt);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
bitaro.cpp:86:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |      scanf("%d", &A[i]);
      |      ~~~~~^~~~~~~~~~~~~

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