oj.uz

답안 #110776

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
110776 2019-05-12T08:11:48 Z MAMBA 007 (CEOI14_007) C++17
0 / 100
 1000 ms 39388 KB 
#include <bits/stdc++.h> 

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define for_all(x) x.begin(),x.end()

typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef long double ld;
typedef complex<ld> point;

inline void fileIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

template<class T , class S>
inline bool smin(T &a, S b) { return (T)b < a ? a = b , 1 : 0; }
template<class T , class S>
inline bool smax(T &a, S b) { return a < (T)b ? a = b , 1 : 0; }

constexpr int N = 1e6 + 10;

constexpr int MOD = 1e9 + 7;

template<typename T>
inline T mod(T &v) { return v = (v % MOD + MOD) % MOD; }
template<typename S, typename T>
inline S add(S &l, T r) { return mod(l += r); }

ll po(ll v, ll u) { return u ? po(v * v % MOD , u >> 1) * (u & 1 ? v : 1) % MOD : 1; }

int n , m;
int s , t , a , b, dist[N];
vector<int> adj[N];
int L , R , Q[N];

void bfs(int so) {
	memset(dist , -1, sizeof(dist));
	dist[so] = 0;
	L = 0, R = 1;
	Q[0] = so;
	while (L < R) {
		int me = Q[L++];
		for (auto e : adj[me])
			if (!~dist[e]) {
				dist[e] = dist[me] + 1;
				Q[R++] = e;
			}
	}
}

int arr[N];

void dfs(int v,  int col) {
	arr[v] == col;
	for (auto e : adj[v])
		if (dist[e] + 1 == dist[v] && arr[e] < col) 
			dfs(e , col);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

#ifndef LOCAL
	//	fileIO("forbidden1");
#endif


	cin >> n >> m >> s >> t >> a >> b;
	rep(i , 0 , m) {
		int u , v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	bfs(s);
	int A = dist[a];
	int B = dist[b];

	dfs(a , 1);
	dfs(b , 2);

	int alpha = 0;
	rep(i , 0 , n + 1)
		if (arr[i] == 3)
			smax(alpha , dist[i]);

	bfs(t);
	int C = dist[a];
	int D = dist[b];

	memset(arr , 0 , sizeof(arr));
	dfs(a , 1);
	dfs(b , 2);

	int beta = 0;
	rep(i , 0 , n + 1)
		if (arr[i] == 3)
			smax(beta , dist[i]);



	int res = min(C - A , D - B);
	if (res < 0) return cout << -1 << endl, 0;

	if (A == B && C == D) 
		res = C - (max(A - alpha , C - beta) + alpha); 
	cout << res << endl;


	return 0;
}

Compilation message

007.cpp: In function 'void dfs(int, int)':
007.cpp:61:9: warning: statement has no effect [-Wunused-value]
  arr[v] == col;
  ~~~~~~~^~~~~~

Subtask #1
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 31616 KB Output is correct
2 Correct 32 ms 31744 KB Output is correct
3 Correct 32 ms 31736 KB Output is correct
4 Correct 37 ms 31744 KB Output is correct
5 Correct 27 ms 31616 KB Output is correct
6 Incorrect 32 ms 31616 KB Output isn't correct
7 Incorrect 35 ms 31736 KB Output isn't correct
8 Correct 33 ms 31744 KB Output is correct
9 Incorrect 32 ms 31744 KB Output isn't correct
10 Correct 32 ms 31736 KB Output is correct
11 Correct 29 ms 31744 KB Output is correct
12 Incorrect 28 ms 31616 KB Output isn't correct
13 Incorrect 33 ms 31608 KB Output isn't correct
14 Incorrect 29 ms 31716 KB Output isn't correct
15 Incorrect 32 ms 31656 KB Output isn't correct
16 Incorrect 32 ms 31616 KB Output isn't correct
17 Incorrect 36 ms 31736 KB Output isn't correct
18 Incorrect 32 ms 31736 KB Output isn't correct
19 Incorrect 33 ms 31736 KB Output isn't correct
20 Incorrect 34 ms 31744 KB Output isn't correct
21 Correct 32 ms 31616 KB Output is correct
22 Incorrect 34 ms 31736 KB Output isn't correct
23 Incorrect 30 ms 31616 KB Output isn't correct
24 Correct 32 ms 31744 KB Output is correct

Subtask #2
0.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 55 ms 33216 KB Output isn't correct
2 Incorrect 67 ms 34040 KB Output isn't correct
3 Incorrect 70 ms 33144 KB Output isn't correct
4 Incorrect 76 ms 34168 KB Output isn't correct
5 Correct 57 ms 33016 KB Output is correct
6 Correct 52 ms 33400 KB Output is correct
7 Incorrect 61 ms 33400 KB Output isn't correct
8 Incorrect 59 ms 33400 KB Output isn't correct
9 Execution timed out 1058 ms 30072 KB Time limit exceeded
10 Execution timed out 1071 ms 34296 KB Time limit exceeded
11 Incorrect 90 ms 34936 KB Output isn't correct
12 Incorrect 105 ms 35576 KB Output isn't correct
13 Incorrect 101 ms 35064 KB Output isn't correct
14 Correct 91 ms 34748 KB Output is correct
15 Incorrect 97 ms 35848 KB Output isn't correct
16 Correct 108 ms 36088 KB Output is correct
17 Incorrect 94 ms 35576 KB Output isn't correct
18 Incorrect 117 ms 35448 KB Output isn't correct
19 Execution timed out 1068 ms 32932 KB Time limit exceeded
20 Execution timed out 1076 ms 35708 KB Time limit exceeded
21 Incorrect 173 ms 38108 KB Output isn't correct
22 Incorrect 147 ms 36588 KB Output isn't correct
23 Correct 167 ms 38008 KB Output is correct
24 Incorrect 182 ms 37924 KB Output isn't correct
25 Incorrect 133 ms 36984 KB Output isn't correct
26 Correct 150 ms 36780 KB Output is correct
27 Incorrect 144 ms 37292 KB Output isn't correct
28 Incorrect 148 ms 37288 KB Output isn't correct
29 Execution timed out 1064 ms 34140 KB Time limit exceeded
30 Execution timed out 1083 ms 36232 KB Time limit exceeded
31 Incorrect 227 ms 39388 KB Output isn't correct
32 Incorrect 182 ms 37500 KB Output isn't correct
33 Correct 144 ms 37624 KB Output is correct
34 Incorrect 192 ms 37844 KB Output isn't correct
35 Incorrect 222 ms 38392 KB Output isn't correct
36 Incorrect 198 ms 38776 KB Output isn't correct
37 Correct 239 ms 38764 KB Output is correct
38 Incorrect 161 ms 38392 KB Output isn't correct
39 Incorrect 173 ms 38392 KB Output isn't correct
40 Execution timed out 1080 ms 36240 KB Time limit exceeded
41 Execution timed out 1076 ms 38344 KB Time limit exceeded