oj.uz

Submission #712929

# Submission time Handle Problem Language Result Execution time Memory
712929 2023-03-20T13:34:23 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 || (dista[next]!=-1 && dista[next] < now.second+1)) 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 && (distb[next]!=-1 && distb[next] < now.second+1)) 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 0 ms 300 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 1 ms 212 KB Output isn't correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Incorrect 1 ms 212 KB Output isn't correct
13 Correct 1 ms 304 KB Output is correct
14 Incorrect 1 ms 212 KB Output isn't correct
15 Correct 1 ms 212 KB Output is correct
16 Incorrect 331 ms 78596 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 300 KB Output is correct
23 Correct 1 ms 300 KB Output is correct
24 Execution timed out 1109 ms 336548 KB Time limit exceeded

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3144 KB Output is correct
2 Incorrect 23 ms 4288 KB Output isn't correct
3 Correct 19 ms 3400 KB Output is correct
4 Incorrect 25 ms 4520 KB Output isn't correct
5 Correct 20 ms 3056 KB Output is correct
6 Correct 18 ms 3460 KB Output is correct
7 Correct 20 ms 3784 KB Output is correct
8 Correct 22 ms 3756 KB Output is correct
9 Execution timed out 1083 ms 335892 KB Time limit exceeded
10 Execution timed out 1020 ms 524288 KB Time limit exceeded
11 Incorrect 39 ms 6064 KB Output isn't correct
12 Correct 58 ms 7472 KB Output is correct
13 Incorrect 49 ms 6540 KB Output isn't correct
14 Correct 47 ms 5556 KB Output is correct
15 Correct 54 ms 7676 KB Output is correct
16 Correct 58 ms 8080 KB Output is correct
17 Correct 48 ms 7156 KB Output is correct
18 Incorrect 49 ms 7228 KB Output isn't correct
19 Execution timed out 1094 ms 362032 KB Time limit exceeded
20 Execution timed out 1099 ms 425844 KB Time limit exceeded
21 Incorrect 87 ms 10520 KB Output isn't correct
22 Correct 67 ms 9008 KB Output is correct
23 Correct 71 ms 10332 KB Output is correct
24 Correct 73 ms 10240 KB Output is correct
25 Incorrect 67 ms 9696 KB Output isn't correct
26 Correct 67 ms 9176 KB Output is correct
27 Correct 77 ms 10460 KB Output is correct
28 Correct 75 ms 10364 KB Output is correct
29 Execution timed out 1103 ms 374168 KB Time limit exceeded
30 Execution timed out 1093 ms 414172 KB Time limit exceeded
31 Incorrect 92 ms 11912 KB Output isn't correct
32 Correct 83 ms 10368 KB Output is correct
33 Correct 78 ms 10692 KB Output is correct
34 Incorrect 88 ms 11180 KB Output isn't correct
35 Incorrect 82 ms 10712 KB Output isn't correct
36 Incorrect 88 ms 11312 KB Output isn't correct
37 Correct 98 ms 12668 KB Output is correct
38 Correct 91 ms 12332 KB Output is correct
39 Correct 98 ms 12368 KB Output is correct
40 Execution timed out 1092 ms 332276 KB Time limit exceeded
41 Execution timed out 1104 ms 370588 KB Time limit exceeded