제출 #334198

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
334198		trthminh	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1688 ms	120684 KiB

bitaro

#include<bits/stdc++.h>

#define X first
#define Y second
#define PB push_back

using namespace std;

const int maxn = 1e5 + 7;
const int oo = 1e9;
const int K = 100;

typedef pair < int, int > pii;

vector < pii > furthest[maxn];
vector < int > v[maxn], r[maxn];
int dis[maxn], busy[maxn], n, m, q, uso[maxn], cnt[maxn];


void spoji(int x)
{
	priority_queue < pii > Q;
	for(int y : r[x])
    {
		cnt[y] = 0;
		Q.push({furthest[y][0].X, y});
	}
	while((!Q.empty()) && furthest[x].size() < K)
    {
		int ind = Q.top().Y;
		if(!uso[furthest[ind][cnt[ind]].Y])
		{
			uso[furthest[ind][cnt[ind]].Y] = 1;
			furthest[x].PB(furthest[ind][cnt[ind]]);
		}
		Q.pop();
        cnt[ind]++;
		if(cnt[ind] < (int)furthest[ind].size())
			Q.push({furthest[ind][cnt[ind]].X, ind});
	}
	for(pii &tmp : furthest[x])
		uso[tmp.Y] = 0, tmp.X++;
	if(furthest[x].size() < K)
		furthest[x].PB({0, x});
}

void precompute()
{
	for(int i = 1;i <= n;i++)
		spoji(i);
}

int lonhoncan(int x)
{
	for(int i = 1;i <= n;i++)
		dis[i] = -oo;
	dis[x] = 0;
	int res = -1;
	for(int i = x; i >= 1 ; i--)
    {
		for(int j : v[i])
			dis[i] = max(dis[i], dis[j] + 1);
		if(!busy[i])
			res = max(res, dis[i]);
	}
	return res;
}

int main()
{
	//freopen("bitaro.inp", "r", stdin);
	cin >> n >> m >> q;
	while (m--)
    {
		int x, y;
        cin >> x >> y;
		v[x].PB(y);
		r[y].PB(x);
	}
	precompute();
	while (q--)
    {
		int st;
		cin >> st;
		int n_people_busy;
		cin >> n_people_busy;
		vector < int > tmp;
		while(n_people_busy--)
        {
			int x; cin >> x;
			tmp.PB(x); busy[x] = 1;
		}

		if(tmp.size() >= K)
			cout << lonhoncan(st) << '\n';
		else{
			int res = -1;
			for(pii ttm : furthest[st]) // K thang lon nhat cua st
				if(!busy[ttm.Y]) res = max(res, ttm.X);
			cout << res << '\n';
		}
		for(int x : tmp) busy[x] = 0;
	}
	return 0;
}

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