제출 #458679

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

bitaro

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
const int B = 320;
int n, m, q;
typedef pair<int, int> pi;
vector<int> prv[maxn];
vector<pi> far[maxn];
vector<int> vis(maxn, -1), val(maxn);
vector<int> y(maxn, -1);

bool cmp(int x, int y){
	return val[x] > val[y];
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> q;
	for (int i = 0; i < m; i ++){
		int x, y;
		cin >> x >> y;
		x --; y --;
		prv[y].push_back(x);
	}
	for (int i = 0; i < n; i ++){
		vector<int> all;
		vector<int> dist[B];
		for (int j = 0; j < (int)prv[i].size(); j ++){
			int x = prv[i][j];
			for (int k = 0; k < far[x].size(); k ++){
				int z = far[x][k].second;
				if (vis[z] != i){
					vis[z] = i;
					all.push_back(z);
					val[z] = far[x][k].first + 1;
				} else{
					val[z] = max(val[z], far[x][k].first + 1);
				}
			}
			if (vis[x] != i){
				vis[x] = i;
				all.push_back(x);
				val[x] = 1;
			}
		}
		all.push_back(i);
		val[i] = 0;
		for (int j = 0; j < all.size(); j ++){
			dist[val[all[j]]].push_back(all[j]);
		}
		int cnt = 0;
		for (int k = B - 1; k >= 0; k --){
			for (int j = 0; j < dist[k].size(); j ++){
				far[i].push_back(make_pair(k, dist[k][j]));
				cnt ++;
				if (cnt == B) break;
			}
		}
	}
	while(q --){
		int t; cin >> t; t --;
		int r; cin >> r;
		for (int i = 0; i < r; i ++){
			int p; cin >> p; y[p - 1] = q;
		}
		if (r >= B){
			vector<int> dp(n, -1);
			for (int i = 0; i <= t; i ++){
				if (y[i] != q){
					dp[i] = max(dp[i], 0);
				}
				for (int j = 0; j < (int)prv[i].size(); j ++){
					if (dp[prv[i][j]] != -1) dp[i] = max(dp[i], dp[prv[i][j]] + 1);
				}
			}
			cout << dp[t] << '\n';
		} else{
			for (int i = 0; i < (int)far[t].size(); i ++){
				if (y[far[t][i].second] != q){
					cout << far[t][i].first << '\n';
					goto done;
				}
			}
			cout << -1 << '\n';
			done: continue;
		}
	}
}

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

bitaro.cpp: In function 'int main()':
bitaro.cpp:31:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |    for (int k = 0; k < far[x].size(); k ++){
      |                    ~~^~~~~~~~~~~~~~~
bitaro.cpp:49:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for (int j = 0; j < all.size(); j ++){
      |                   ~~^~~~~~~~~~~~
bitaro.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    for (int j = 0; j < dist[k].size(); j ++){
      |                    ~~^~~~~~~~~~~~~~~~

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