제출 #199958

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
199958		dennisstar	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	25 ms	12280 KiB

bitaro

#include <bits/stdc++.h>
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define all(V) (V).begin(), (V).end()
using namespace std;
typedef vector<int> vim;
typedef pair<int, int> pii;

const int MAX=400;

int N, M, Q, ans[100010], chk[100010], ar[100010];
vim adj[100010], qu[100010], C[100010];
vector<pii> B[100010];

int main() {
	scanf("%d %d %d", &N, &M, &Q);
	for (int i=0, u, v; i<M; i++) scanf("%d %d", &u, &v), adj[v].eb(u);
	for (int i=1, t, y; i<=Q; i++) {
		scanf("%d %d", &t, &y); qu[t].eb(i);
		C[i].resize(y); for (auto &j:C[i]) scanf("%d", &j); sort(all(C[i])); C[i].eb((1<<30));
	}
	for (int i=1; i<=N; i++) {
		B[i].eb(0, i);
		for (auto &j:adj[i]) {
			vector<pii> im;
			int b=0;
			for (auto &i:B[i]) {
				while (b<B[j].size()&&i.fi<B[j][b].fi+1&&im.size()<MAX) {
					if (!chk[B[j][b].se]) im.eb(B[j][b].fi+1, B[j][b].se), chk[B[j][b].se]=1;
					b++;
				}
				if (im.size()>=MAX) break;
				if (!chk[i.se]) im.eb(i), chk[i.se]=1;
			}
			for (auto &k:im) chk[k.se]=0;
			B[i]=im;
		}
		for (auto &j:qu[i]) {
			ans[j]=-1;
			if (B[i].size()<MAX||C[j].size()<MAX) for (auto &k:B[i]) if (*lower_bound(all(C[j]), k.se)!=k.se) { ans[j]=k.fi; break; }
			else {
				for (int k=1; k<=i; k++) {
					ar[k]=(*lower_bound(all(C[j]), k)==k?-1e6:0);
					for (auto &l:adj[k]) ar[k]=max(ar[k], ar[l]+1);
				}
				ans[j]=ar[i]<0?-1:ar[i];
			}
		}
	}
	for (int i=1; i<=Q; i++) printf("%d\n", ans[i]);
	return 0;
}

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

bitaro.cpp: In function 'int main()':
bitaro.cpp:30:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (b<B[j].size()&&i.fi<B[j][b].fi+1&&im.size()<MAX) {
            ~^~~~~~~~~~~~
bitaro.cpp:42:7: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
    if (B[i].size()<MAX||C[j].size()<MAX) for (auto &k:B[i]) if (*lower_bound(all(C[j]), k.se)!=k.se) { ans[j]=k.fi; break; }
       ^
bitaro.cpp:18: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:19:54: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=0, u, v; i<M; i++) scanf("%d %d", &u, &v), adj[v].eb(u);
                                ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
bitaro.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &t, &y); qu[t].eb(i);
   ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:22:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   C[i].resize(y); for (auto &j:C[i]) scanf("%d", &j); sort(all(C[i])); C[i].eb((1<<30));
                                      ~~~~~^~~~~~~~~~

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