제출 #1127579

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127579		liemdinat	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	939 ms	277888 KiB

bitaro

#include <bits/stdc++.h>
#define FOR(i, k, n) for(int i = k; i <= n; i++)
#define FORD(i, k, n) for(int i = k; i >= n; i--)
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPD(i, n) for(int i = n - 1; i >= 0; i--)
#define ii pair<int,int>
#define trii pair<int,ii>
#define fi first
#define se second
#define int long long
#define vi vector<int>
#define pb push_back
#define all(x, n) (x) + 1, (x) + n + 1
#define allv(x) (x).begin(), (x).end()
#define vii vector<ii>
#define sz(x) ((int)x.size())

using namespace std;
const int N = 1e5 + 5;
const int B = 100;
vi rg[N];
vii lps[N];
int bs[N];
int dp[N];
int n, m, q;
bool ava[N];
int from[N];

void cal(int t)
{
	FOR(i, 1, t)
	{
		if (ava[i]) dp[i] = 0;
		else dp[i] = -1;
		for (int j : rg[i])
		{
			if (dp[j] != -1) dp[i] = max(dp[i], dp[j] + 1); 
		}
	}
	cout << dp[t] << '\n';
}

int32_t main()
{
    iostream::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> q;
    FOR(i, 1, m)
    {
    	int u, v; cin >> u >> v;
    	rg[v].pb(u);
    }
    memset(from, -1, sizeof(from));
    FOR(i, 1, n)
    {
    	static vi fidx;
    	fidx.clear();
    	lps[i].pb({0, i});
    	for (int j : rg[i])
    	{
    		for (ii &x : lps[j])
    		{
    			if (from[x.se] == -1)
    			{
    				fidx.pb(x.se);
    				from[x.se] = x.fi + 1; 
    			}
    			else
    			{
    				from[x.se] = max(from[x.se], x.fi + 1);
    			}
    		}
    	}
    	for (int x : fidx)
    	{
    		lps[i].pb({from[x], x});
    	}
    	sort(allv(lps[i])); reverse(allv(lps[i]));
    	while(sz(lps[i]) > B) lps[i].pop_back();
    	for (int x : fidx)
    	{
    		from[x] = -1;
    	}	
    }
    memset(ava, true, sizeof ava);
    FOR(i, 1, q)
    {
    	int t, y; cin >> t >> y;
    	FOR(j, 1, y)
    	{
    		cin >> bs[j];
    	}
    	FOR(i, 1, y) ava[bs[i]] = false;
    	if (y >= B)
    	{		
    		cal(t);
    	}
    	else
    	{
    		bool f = false;
    		REP(i, sz(lps[t]))
    		{
    			if (ava[lps[t][i].se])
    			{
    				cout << lps[t][i].fi << '\n';
    				f = true;
    				break;
    			}
    		}
    		if (!f)
			{
				cout << -1 << '\n';
			}
    	}
    	FOR(i, 1, y) ava[bs[i]] = true;
    }
    return 0;
}

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