제출 #117039

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
117039		PeppaPig	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2051 ms	311428 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);
		for(int v : g[u]) if(dp[v] != -1e9) 
            dp[u] = max(dp[u], dp[v] + 1);
	}
}
 
vector<pii> pre[N];
int mx[N], all[N];
 
void preprocess() {
    fill_n(mx, N, -1);
	for(int i = 1; i <= n; i++) pre[i].emplace_back(0, i);
	for(int u = 1; u <= n; u++) {
        int ptr = 0;
        all[++ptr] = u, mx[u] = 0;
        for(int v : g[u]) for(pii p : pre[v]) {
            mx[p.y] = max(mx[p.y], p.x + 1);
            all[++ptr] = p.y;
        }
        for(int i = 1; i <= ptr; i++) {
            pre[u].emplace_back(mx[all[i]], all[i]);
            mx[all[i]] = -1;
        }
        sort(pre[u].begin(), pre[u].end(), greater<pii>());
        while(pre[u].size() > B) pre[u].pop_back();
	}
}
 
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[b].emplace_back(a);
	}
	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] != -1e9) printf("%d\n", dp[t]);
			else printf("-1\n");
		} else {
			bool valid = false;
			for(int i : block) tchk[i] = true;
            for(pii p : pre[t]) if(!tchk[p.y]) {
				valid = true;
				printf("%d\n", p.x);
				break;
			}
			if(!valid) printf("-1\n");
			for(int i : block) tchk[i] = false;
		}
	}
 
	return 0;
}

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

bitaro.cpp: In function 'int main()':
bitaro.cpp:52: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:54: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:60: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:63:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a);
    ~~~~~^~~~~~~~~~

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