oj.uz

Submission #712928

# Submission time Handle Problem Language Result Execution time Memory
712928 2023-03-20T13:32:09 Z yuseok0803 007 (CEOI14_007) C++14
0 / 100
 1000 ms 524288 KB 
#include <stdio.h>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stack>
#include <ctype.h>
#define p(x,y) pair<x, y>
#define pii pair<int, int>
#define v(x) vector<x>
#define q(x) queue<x>
#define pq(x) priority_queue<x>
#define uppq(x, comp) priority_queue<x, vector<x>, comp>
#define st(x) set<x>  
#define m(x, y) map<x, y>
#define fi(s,e) for(int i=s;i<e;i++)
#define fj(s,e) for(int j=s;j<e;j++)
#define fk(s,e) for(int k=s;k<e;k++)
typedef long long int ll;
typedef unsigned long long int ull;
typedef __int128 ulll;
using namespace std;

int n,m;
int s,d,a,b;
v(int) pushvec;
v(v(int)) vec;
int dista[200010], distb[200010];

void spreada(int x){
	q(p(pii, int)) qu;
	qu.push({{x,x}, 0});
	while(!qu.empty()){
		p(pii, int) now = qu.front();
		qu.pop();
		
		if(now.second > dista[now.first.first] && dista[now.first.first] != -1) continue;
		
		dista[now.first.first]=now.second;
		int sz = vec[now.first.first].size();
		fi(0,sz){
			int next = vec[now.first.first][i];
			if(next == now.first.second) continue;
			qu.push({{next, now.first.first}, now.second+1});
		}
	}
	return;
}

void spreadb(int x){
	q(p(pii, int)) qu;
	qu.push({{x,x}, 0});
	while(!qu.empty()){
		p(pii, int) now = qu.front();
		qu.pop();
		
		if(now.second > distb[now.first.first] && distb[now.first.first] != -1) continue;
		
		distb[now.first.first]=now.second;
		int sz = vec[now.first.first].size();
		fi(0,sz){
			int next = vec[now.first.first][i];
			if(next == now.first.second) continue;
			qu.push({{next, now.first.first}, now.second+1});
		}
	}
	return;
}

int find(int now){
	int sz = vec[now].size();
	int ans = dista[now];
	fi(0,sz){
		int next = vec[now][i];
		if(dista[next]==dista[now]-1 && dista[next]==distb[next]){
			ans = min(ans, find(next));
		}
	}
	return ans;
}

int main(void){
	scanf("%d%d%d%d%d%d",&n,&m,&s,&d,&a,&b);
	
	fi(0,n+1) vec.push_back(pushvec);
	fi(0,m){
		int s,e;
		scanf("%d%d",&s,&e);
		vec[s].push_back(e);
		vec[e].push_back(s);
	}
	
	fi(1,n+1){
		dista[i]=-1;
		distb[i]=-1;
	}
	
	spreada(a);
	spreadb(b);
	
	int ans = min(dista[d]-dista[s], distb[d]-distb[s]);
	if(dista[s]==distb[s] && distb[s]==distb[d]){
		int divds, divdb;
		divds = find(s);
		divdb = find(d);
		if(divds > divdb) ans--;
	}
	
	printf("%d\n", max(ans, -1));
	return 0;
}

Compilation message

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

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 304 KB Output isn't correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 0 ms 304 KB Output isn't correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Incorrect 1 ms 304 KB Output isn't correct
13 Correct 1 ms 368 KB Output is correct
14 Incorrect 1 ms 212 KB Output isn't correct
15 Correct 1 ms 304 KB Output is correct
16 Incorrect 448 ms 78668 KB Output isn't correct
17 Incorrect 1 ms 340 KB Output isn't correct
18 Incorrect 1 ms 340 KB Output isn't correct
19 Correct 1 ms 304 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 308 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Execution timed out 1093 ms 192280 KB Time limit exceeded

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3240 KB Output is correct
2 Incorrect 22 ms 4636 KB Output isn't correct
3 Correct 20 ms 3512 KB Output is correct
4 Incorrect 23 ms 4808 KB Output isn't correct
5 Correct 17 ms 3144 KB Output is correct
6 Correct 19 ms 3576 KB Output is correct
7 Correct 18 ms 3912 KB Output is correct
8 Correct 20 ms 3896 KB Output is correct
9 Execution timed out 1110 ms 413632 KB Time limit exceeded
10 Runtime error 805 ms 524288 KB Execution killed with signal 9
11 Incorrect 41 ms 6980 KB Output isn't correct
12 Correct 58 ms 8844 KB Output is correct
13 Incorrect 79 ms 7572 KB Output isn't correct
14 Correct 39 ms 6376 KB Output is correct
15 Correct 58 ms 8956 KB Output is correct
16 Correct 61 ms 9448 KB Output is correct
17 Correct 52 ms 8388 KB Output is correct
18 Incorrect 55 ms 8456 KB Output isn't correct
19 Execution timed out 1107 ms 444872 KB Time limit exceeded
20 Runtime error 968 ms 524288 KB Execution killed with signal 9
21 Incorrect 88 ms 12356 KB Output isn't correct
22 Correct 71 ms 10644 KB Output is correct
23 Correct 76 ms 12148 KB Output is correct
24 Correct 68 ms 12020 KB Output is correct
25 Incorrect 76 ms 11356 KB Output isn't correct
26 Correct 76 ms 10772 KB Output is correct
27 Correct 92 ms 12348 KB Output is correct
28 Correct 98 ms 12292 KB Output is correct
29 Execution timed out 1098 ms 458056 KB Time limit exceeded
30 Execution timed out 1036 ms 524288 KB Time limit exceeded
31 Incorrect 88 ms 14128 KB Output isn't correct
32 Correct 93 ms 12164 KB Output is correct
33 Correct 79 ms 12624 KB Output is correct
34 Incorrect 92 ms 13268 KB Output isn't correct
35 Incorrect 78 ms 12612 KB Output isn't correct
36 Incorrect 86 ms 13132 KB Output isn't correct
37 Correct 117 ms 15032 KB Output is correct
38 Correct 119 ms 14684 KB Output is correct
39 Correct 107 ms 14660 KB Output is correct
40 Execution timed out 1092 ms 431468 KB Time limit exceeded
41 Execution timed out 1085 ms 520548 KB Time limit exceeded