Submission #199953

#	Time	Username	Problem	Language	Result	Execution time	Memory
199953		dennisstar	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2017 ms	22332 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=300;

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;
			for (int a=0, b=0; (a<B[i].size()||b<B[j].size())&&im.size()<MAX; ) {
				if (b>=B[j].size() || (a<B[i].size()&&B[i][a].fi>=B[j][b].fi+1)) chk[B[i][a].se]=1, im.eb(B[i][a]), a++;
				else chk[B[j][b].se]=1, im.eb(B[j][b].fi+1, B[j][b].se), b++;
				while (a<B[i].size()&&chk[B[i][a].se]) a++;
				while (b<B[j].size()&&chk[B[j][b].se]) b++;
			}
			for (auto &k:im) chk[k.fi]=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;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:28:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int a=0, b=0; (a<B[i].size()||b<B[j].size())&&im.size()<MAX; ) {
                        ~^~~~~~~~~~~~
bitaro.cpp:28:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int a=0, b=0; (a<B[i].size()||b<B[j].size())&&im.size()<MAX; ) {
                                       ~^~~~~~~~~~~~
bitaro.cpp:29:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (b>=B[j].size() || (a<B[i].size()&&B[i][a].fi>=B[j][b].fi+1)) chk[B[i][a].se]=1, im.eb(B[i][a]), a++;
         ~^~~~~~~~~~~~~
bitaro.cpp:29:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (b>=B[j].size() || (a<B[i].size()&&B[i][a].fi>=B[j][b].fi+1)) chk[B[i][a].se]=1, im.eb(B[i][a]), a++;
                            ~^~~~~~~~~~~~
bitaro.cpp:31:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (a<B[i].size()&&chk[B[i][a].se]) a++;
            ~^~~~~~~~~~~~
bitaro.cpp:32:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (b<B[j].size()&&chk[B[j][b].se]) b++;
            ~^~~~~~~~~~~~
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: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 0 / 86