Submission #311920

#	Time	Username	Problem	Language	Result	Execution time	Memory
311920		arnold518	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1823 ms	176676 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const int SQ = 100;
const int INF = 1e9;

int N, M, Q;
vector<int> adj[MAXN+10];
int ans[MAXN+10];
int dp[MAXN+10];
int val[MAXN+10];

struct Data
{
	int T, P;
	vector<int> V;
};
Data A[MAXN+10];
vector<int> P[MAXN+10];

vector<pii> dp2[MAXN+10];
bool chk[MAXN+10];

int main()
{
	memset(ans, -1, sizeof(ans));
	scanf("%d%d%d", &N, &M, &Q);
	for(int i=1; i<=M; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		adj[v].push_back(u);
	}
	for(int i=1; i<=Q; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		A[i].T=a; A[i].P=i;
		while(b--)
		{
			int t;
			scanf("%d", &t);
			A[i].V.push_back(t);
		}

		if(A[i].V.size()>=SQ)
		{
			for(int j=1; j<=N; j++) dp[j]=0;
			for(auto it : A[i].V) dp[it]=-INF;
			for(int j=1; j<=N; j++) for(auto nxt : adj[j]) dp[j]=max(dp[j], dp[nxt]+1);
			if(dp[A[i].T]>=0) ans[i]=dp[A[i].T];
		}
		else P[A[i].T].push_back(i);
	}

	for(int now=1; now<=N; now++)
	{
		dp2[now].push_back({0, now});
		vector<int> V;
		for(auto nxt : adj[now])
		{
			for(auto it : dp2[nxt])
			{
				val[it.second]=max(val[it.second], it.first+1);
				V.push_back(it.second);
			}
		}
		
		for(auto it : V)
		{
			if(chk[it]) continue;
			chk[it]=true;
			dp2[now].push_back({val[it], it});
		}
		for(auto it : V) chk[it]=false;
		sort(dp2[now].begin(), dp2[now].end(), greater<pii>());
		while(dp2[now].size()>SQ) dp2[now].pop_back();
		for(auto it : V) val[it]=0;

		for(auto it : dp2[now]) chk[it.second]=false;
		for(auto it : P[now])
		{
			for(auto pt : A[it].V) chk[pt]=true;
			for(auto jt : dp2[now])
			{
				if(!chk[jt.second])
				{
					ans[it]=jt.first;
					break;
				}
			}
			for(auto pt : A[it].V) chk[pt]=false;
		}
	}

	for(int i=1; i<=Q; i++) printf("%d\n", ans[i]);
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |  scanf("%d%d%d", &N, &M, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:47:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |    scanf("%d", &t);
      |    ~~~~~^~~~~~~~~~

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