제출 #220910

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
220910		patrikpavic2	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2093 ms	41988 KiB

bitaro

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

#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 = 30;

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];

void spoji(int x){
	vector < pii > tmp;
	for(int y : r[x]){
		for(pii tmp2 : tko[y])
			tmp.PB({tmp2.X + 1, tmp2.Y});
	}
	sort(tmp.rbegin(), tmp.rend());
	for(pii tmp2 : tmp){
		if(tko[x].size() == K) break;
		if(uso[tmp2.Y]) continue;
		uso[tmp2.Y] = 1;
		tko[x].PB(tmp2);
	}
	for(pii tmp2 : tko[x])
		uso[tmp2.Y] = 0;
	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;
}

컴파일 시 표준 에러 (stderr) 메시지

bitaro.cpp: In function 'int main()':
bitaro.cpp:61: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:63: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:69: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:70: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:73: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: 0 / 86