제출 #883731

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
883731		Hakiers	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	1554 ms	418208 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 1e5 + 7;
constexpr int SQRT = 300;
vector<int> G[MAXN];
vector<pair<int, int>> dp[MAXN];
int dist[MAXN];
bool visited[MAXN];
int n, m, q;

void compute(int v){
	vector<int> tmp;
	dist[v] = 0;
	tmp.push_back(v);
	
	for(auto u : G[v]){
		for(auto [D, k] : dp[u]){	
			if(!dist[k])
				tmp.push_back(k);
			dist[k] = max(dist[k], D + 1);
		}
	}
	
	for(auto x : tmp){
		dp[v].push_back({dist[x], x});
		dist[x] = 0;
	}
	
	sort(dp[v].begin(), dp[v].end());
	reverse(dp[v].begin(), dp[v].end());
	
	while(dp[v].size() > SQRT)
		dp[v].pop_back();

}


void dfs(int v){
	if(dist[v] != -1)
		dist[v] = 0;
	visited[v] = 1;
	
	for(auto u : G[v]){
		if(!visited[u]) dfs(u);
		
		if(dist[u] == -1) continue;
		dist[v] = max(dist[v], dist[u] + 1);
	}
}

int ans1(int v, int l){
	
	for(int i = 1; i <= l; i++){
		int u;
		cin >> u;
		dist[u] = -1;
	}
		
	dfs(v);
	int res = dist[v];
	
	for(int i = 1; i <= n; i++)
		visited[i] = dist[i] = 0;
	
	return res;
}

int ans2(int v, int l){
	int it = 0;
	int ans = -1;
	for(int i = 1; i <= l; i++){
		int u;
		cin >> u;
		
		if(it < dp[v].size() && dp[v][it].second == u)
			it++;
		else if(it < dp[v].size())
			ans = max(ans, dp[v][it].first);
	}
	
	if(it < dp[v].size())
		ans = max(ans, dp[v][it].first);
		
	return ans;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> q;
	
	for(int i = 1; i <= m; i++){
		int u, v;
		cin >> u >> v;
		G[v].push_back(u);
	}
	
	for(int i = 1; i <= n; i++)
		compute(i);
	
	
	for(int i = 1; i <= q; i++){
		int v, l;
		cin >> v >> l;
		if(l >= SQRT) cout << ans1(v, l) << "\n";
		else cout << ans2(v, l) << "\n";
	}
}

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

bitaro.cpp: In function 'int ans1(int, int)':
bitaro.cpp:63:24: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   63 |   visited[i] = dist[i] = 0;
      |                ~~~~~~~~^~~
bitaro.cpp: In function 'int ans2(int, int)':
bitaro.cpp:75:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   if(it < dp[v].size() && dp[v][it].second == u)
      |      ~~~^~~~~~~~~~~~~~
bitaro.cpp:77:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   else if(it < dp[v].size())
      |           ~~~^~~~~~~~~~~~~~
bitaro.cpp:81:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  if(it < dp[v].size())
      |     ~~~^~~~~~~~~~~~~~

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