oj.uz

답안 #447746

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
447746 2021-07-27T12:42:16 Z Nima_Naderi 007 (CEOI14_007) C++14
100 / 100
 304 ms 35776 KB 
//In the name of God
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 2e5 + 10;
const ll MXM = 6e5 + 10;
const ll INF = 1e9;
ll n, m, k, t, s[2], Src[4];
ll dis[4][MXN], Q[MXN];
vector<ll> adj[MXN];
bool vis[MXN];
void BFS(ll f, ll src){
	fill(dis[f], dis[f] + MXN, INF);
	memset(vis, 0, sizeof vis);
	ll L = 0, R = 0; Src[f] = src;
	dis[f][src] = 0, Q[R ++] = src, vis[src] = 1;
	while(L < R){
		ll u = Q[L ++];
		for(auto v : adj[u]){
			if(!vis[v]){
				dis[f][v] = dis[f][u] + 1;
				vis[v] = 1, Q[R ++] = v;
			}
		}
	}
}
inline bool in_path(ll u, ll f0, ll f1){
	ll s = Src[f0], e = Src[f1];
	return (dis[f0][u] + dis[f1][u] == dis[f0][e]);
}
ll check(ll f, ll x){//tz check
	if(dis[f][k] + x > dis[f][t]) return 1;
	if(dis[f][k] + x < dis[f][t]) return 0;
	return 2;
}
bool check(ll x){
	ll ck0 = check(0, x), ck1 = check(1, x);
	if(ck0 == 1 || ck1 == 1) return 0;
	if(ck0 == 0 || ck1 == 0) return 1;
	//return (!check(0, x)) && (!check(1, x));
	ll tz = 0, km = 0;
	for(int i = 1; i <= n; i ++){
		if(in_path(i, 2, 0) && in_path(i, 2, 1)){
			km = max(km, dis[2][i]);
		}
		if(in_path(i, 3, 0) && in_path(i, 3, 1)){
			tz = max(tz, dis[3][i]);
		}
	}
	return !(tz > km + x);
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	cin >> n >> m >> k >> t >> s[0] >> s[1];
	for(int i = 1; i <= m; i ++){
		ll u, v; cin >> u >> v;
		adj[u].push_back(v), adj[v].push_back(u);
	}
	BFS(0, s[0]), BFS(1, s[1]);
	BFS(2, k), BFS(3, t);
	if(!check(0)) return cout << -1, 0;
	ll low = 0, hig = n + 1;
	while(hig - low > 1){
		ll mid = (low + hig) / 2;
		if(check(mid))	low = mid;
		else			hig = mid;
	}
	cout << low << '\n';
	return 0;
}
// I was born to be making history.
// N.N

Compilation message

007.cpp: In function 'bool in_path(ll, ll, ll)':
007.cpp:30:5: warning: unused variable 's' [-Wunused-variable]
   30 |  ll s = Src[f0], e = Src[f1];
      |     ^

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11468 KB Output is correct
2 Correct 6 ms 11468 KB Output is correct
3 Correct 6 ms 11468 KB Output is correct
4 Correct 6 ms 11468 KB Output is correct
5 Correct 7 ms 11420 KB Output is correct
6 Correct 6 ms 11420 KB Output is correct
7 Correct 6 ms 11468 KB Output is correct
8 Correct 6 ms 11468 KB Output is correct
9 Correct 6 ms 11468 KB Output is correct
10 Correct 6 ms 11420 KB Output is correct
11 Correct 7 ms 11468 KB Output is correct
12 Correct 6 ms 11468 KB Output is correct
13 Correct 7 ms 11468 KB Output is correct
14 Correct 6 ms 11424 KB Output is correct
15 Correct 6 ms 11468 KB Output is correct
16 Correct 6 ms 11468 KB Output is correct
17 Correct 6 ms 11468 KB Output is correct
18 Correct 7 ms 11424 KB Output is correct
19 Correct 7 ms 11468 KB Output is correct
20 Correct 7 ms 11468 KB Output is correct
21 Correct 6 ms 11468 KB Output is correct
22 Correct 6 ms 11468 KB Output is correct
23 Correct 6 ms 11468 KB Output is correct
24 Correct 7 ms 11468 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 13504 KB Output is correct
2 Correct 41 ms 14340 KB Output is correct
3 Correct 30 ms 13724 KB Output is correct
4 Correct 40 ms 14560 KB Output is correct
5 Correct 30 ms 13548 KB Output is correct
6 Correct 31 ms 13636 KB Output is correct
7 Correct 33 ms 13892 KB Output is correct
8 Correct 36 ms 13996 KB Output is correct
9 Correct 48 ms 15556 KB Output is correct
10 Correct 174 ms 28316 KB Output is correct
11 Correct 68 ms 16068 KB Output is correct
12 Correct 106 ms 17676 KB Output is correct
13 Correct 93 ms 16788 KB Output is correct
14 Correct 54 ms 15696 KB Output is correct
15 Correct 78 ms 17348 KB Output is correct
16 Correct 84 ms 17752 KB Output is correct
17 Correct 75 ms 16952 KB Output is correct
18 Correct 82 ms 17048 KB Output is correct
19 Correct 160 ms 21176 KB Output is correct
20 Correct 214 ms 30088 KB Output is correct
21 Correct 103 ms 19652 KB Output is correct
22 Correct 118 ms 18636 KB Output is correct
23 Correct 116 ms 19548 KB Output is correct
24 Correct 117 ms 19484 KB Output is correct
25 Correct 134 ms 19140 KB Output is correct
26 Correct 102 ms 18740 KB Output is correct
27 Correct 120 ms 19812 KB Output is correct
28 Correct 176 ms 19776 KB Output is correct
29 Correct 179 ms 23828 KB Output is correct
30 Correct 246 ms 31112 KB Output is correct
31 Correct 152 ms 20900 KB Output is correct
32 Correct 139 ms 19800 KB Output is correct
33 Correct 123 ms 19872 KB Output is correct
34 Correct 143 ms 20548 KB Output is correct
35 Correct 130 ms 19956 KB Output is correct
36 Correct 125 ms 20292 KB Output is correct
37 Correct 159 ms 21572 KB Output is correct
38 Correct 159 ms 21336 KB Output is correct
39 Correct 173 ms 21544 KB Output is correct
40 Correct 229 ms 27844 KB Output is correct
41 Correct 304 ms 35776 KB Output is correct