Submission #454820

#	Time	Username	Problem	Language	Result	Execution time	Memory
454820		kingfran1907	007 (CEOI14_007)	C++14	44 / 100	370 ms	17720 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);
	
	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 {
		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]);
			}
		}
		int ps = dp[s];
		int pd = dp[d];
		
		if (ps + ax < pd) printf("%d\n", ax - 1);
		else printf("%d\n", ax);
	}
	return 0;
}

Compilation message (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: 23 / 30
• Subtask 2: 21 / 70