Submission #220914

#	Time	Username	Problem	Language	Result	Execution time	Memory
220914		patrikpavic2	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1290 ms	117364 KiB

bitaro

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

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

using namespace std;

const int N = 1e5 + 500;
const int INF = 0x3f3f3f3f;
const int K = 100;

typedef pair < int, int > pii;

vector < pii > tko[N];
vector < int > v[N], r[N];
int dis[N], zab[N], n, m, q, uso[N], gdje[N];

priority_queue < pii > Q;

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

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

int seljacki(int x){
	for(int i = 1;i <= n;i++)
		dis[i] = -INF;
	dis[x] = 0;
	int ret = -1;
	for(int i = x; i ; i--){
		for(int j : v[i])
			dis[i] = max(dis[i], dis[j] + 1);
		if(!zab[i])
			ret = max(ret, dis[i]);
	}
	return ret;
}

int main(){
	scanf("%d%d%d", &n, &m, &q);
	for(;m--;){
		int x, y; scanf("%d%d", &x, &y);
		v[x].PB(y);
		r[y].PB(x);
	}
	precompute();
	for(;q--;){
		int st; scanf("%d", &st);
		int kol; scanf("%d", &kol);
		vector < int > tmp;
		for(;kol--;){
			int x; scanf("%d", &x);
			tmp.PB(x); zab[x] = 1;
		}
		
		if((int)tmp.size() >= K)
			printf("%d\n", seljacki(st));
		else{
			int ret = -1;
			for(pii bla : tko[st])
				if(!zab[bla.Y]) ret = max(ret, bla.X);
			printf("%d\n", ret);
		}
		for(int x : tmp) zab[x] = 0;
	}
	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:69:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:75:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int st; scanf("%d", &st);
           ~~~~~^~~~~~~~~~~
bitaro.cpp:76:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int kol; scanf("%d", &kol);
            ~~~~~^~~~~~~~~~~~
bitaro.cpp:79:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x; scanf("%d", &x);
           ~~~~~^~~~~~~~~~

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