제출 #454809

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
454809		kingfran1907	007 (CEOI14_007)	C++14	10 / 100	285 ms	16144 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];

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);
			}
		}
	}
}

int f(int x) {
	int out = 0;
	while (true) {
		int ind = -1;
		for (int tren : graph[x]) {
			if (disa[tren] < disa[x] && disb[tren] < disb[x]) ind = tren;
		}
		if (ind == -1) break;
		out++;
		x = ind;
	}
	return out;
}

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);
	
	int ax = disa[d] - disa[s];
	int bx = disb[d] - disb[s];
	if (ax > bx) swap(ax, bx);
	
	if (ax < 0 || bx < 0) printf("-1\n");
	else if (ax + 1 == bx) printf("%d\n", ax);
	else {
		int ps = f(s);
		int pd = f(d);
		
		if (ps + ax < pd) printf("%d\n", ax - 1);
		else printf("%d\n", ax);
	}
	return 0;
}

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

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

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