제출 #455040

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
455040		kingfran1907	007 (CEOI14_007)	C++14	0 / 100	301 ms	17688 KiB

007

#include <bits/stdc++.h>
#define X first
#define Y second
 
using namespace std;
typedef long long llint;
 
const int maxn = 2e5+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 18;
const int off = 1 << logo;
const int treesiz = off << 1;

int n, m;
int s, d, a, b;
vector< int > graph[maxn];
int disa[maxn], disb[maxn];
int dp[maxn];

void calc(int x, int dis[maxn]) {
	for (int i = 1; i <= n; i++) dis[i] = -1;
	
	queue< int > q;
	dis[x] = 0;
	q.push(x);
	
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		
		for (int tren : graph[x]) {
			if (dis[tren] == -1) {
				dis[tren] = dis[x] + 1;
				q.push(tren);
			}
		}
	}
}

bool cmp(int a, int b) {
	return disa[a] < disa[b];
}

int main() {
	scanf("%d%d", &n, &m);
	scanf("%d%d%d%d", &s, &d, &a, &b);
	
	for (int i = 0; i < m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	calc(a, disa);
	calc(b, disb);
	
	vector< int > v;
	for (int i = 1; i <= n; i++) v.push_back(i);
	sort(v.begin(), v.end(), cmp);
	
	for (int i : v) {
		dp[i] = 0;
		for (int tren : graph[i]) {
			if (disa[i] > disa[tren] && disb[i] > disb[tren]) dp[i] = max(dp[i], 1 + dp[tren]);
		}
	}
	
	if (disa[s] != disb[s] || disa[d] != disb[d]) {
		int sol = min(disa[d] - disa[s], disb[d] - disb[s]);
		printf("%d\n", max(sol, -1));
	} else {
		int sol = disa[d] - disa[s];
		if (dp[d] < dp[s]) sol--;
		printf("%d\n", max(sol, -1));
	}
	return 0;
}

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

007.cpp: In function 'int main()':
007.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
007.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  scanf("%d%d%d%d", &s, &d, &a, &b);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%d%d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70