Submission #114930

#	Time	Username	Problem	Language	Result	Execution time	Memory
114930		PeppaPig	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	24 ms	14208 KiB

bitaro

#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 1e5+5;
const int B = 320;

int n, m, q;
int dp[N], chk[N];
vector<int> g[N];

void solve(vector<int> &v) {
	fill_n(dp, N, -1e9);
	memset(chk, 0, sizeof chk);
	for(int i : v) chk[i] = true;
	for(int u = 1; u <= n; u++) {
		if(!chk[u]) dp[u] = max(dp[u], 0);
		if(dp[u] == -1e9) continue;
		for(int v : g[u]) dp[v] = max(dp[v], dp[u] + 1);
	}
}

vector<pii> merge(vector<pii> &a, vector<pii> &b) {
	vector<pii> ret;
	int l = 0, r = 0;
	while(l < a.size() && r < b.size()) {
		if(a[l] > b[r]) ret.emplace_back(a[l++]);
		else ret.emplace_back(b[r++]);
	}
	while(l < a.size()) ret.emplace_back(a[l++]);
	while(r < b.size()) ret.emplace_back(b[r++]);
	ret.resize(B);
	return ret;
}

vector<pii> pre[N];

void preprocess() {
	for(int i = 1; i <= n; i++) {
		pre[i] = vector<pii>(B, pii(-1, -1));
		pre[i][0] = pii(0, i);
	}
	for(int u = 1; u <= n; u++) for(int v : g[u]) {
		vector<pii> now(B, pii(-1, -1));
		for(int i = 0; i < B; i++) if(pre[u][i].x != -1) 
			now[i] = pii(pre[u][i].x + 1, pre[u][i].y);
		pre[v] = merge(now, pre[v]);
	}
}

bitset<N> tchk;

int main() {
	scanf("%d %d %d", &n, &m, &q);
	for(int i = 1, a, b; i <= m; i++) {
		scanf("%d %d", &a, &b);
		if(a > b) swap(a, b);
		g[a].emplace_back(b);
	}
	preprocess();
	for(int i = 1, t, y; i <= q; i++) {
		scanf("%d %d", &t, &y);
		vector<int> block;
		for(int i = 1, a; i <= y; i++) {
			scanf("%d", &a);
			block.emplace_back(a);
		}
		if(y >= B) {
			solve(block);
			if(dp[t] != -1) printf("%d\n", dp[t]);
			else printf("-1\n");
		} else {
			bool valid = false;
			for(int i : block) tchk[i] = true;
			for(int i = 0; i < B; i++) if(pre[t][i].x != -1 && !tchk[pre[t][i].y]) {
				valid = true;
				printf("%d\n", pre[t][i].x);
				break;
			}
			if(!valid) printf("-1\n");
			for(int i : block) tchk[i] = false;
		}
	}

	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'std::vector<std::pair<int, int> > merge(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&)':
bitaro.cpp:30:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(l < a.size() && r < b.size()) {
        ~~^~~~~~~~~~
bitaro.cpp:30:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(l < a.size() && r < b.size()) {
                        ~~^~~~~~~~~~
bitaro.cpp:34:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(l < a.size()) ret.emplace_back(a[l++]);
        ~~^~~~~~~~~~
bitaro.cpp:35:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(r < b.size()) ret.emplace_back(b[r++]);
        ~~^~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:58: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:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &t, &y);
   ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:69:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a);
    ~~~~~^~~~~~~~~~

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