oj.uz

Submission #712930

# Submission time Handle Problem Language Result Execution time Memory
712930 2023-03-20T13:35:19 Z yuseok0803 007 (CEOI14_007) C++14
20 / 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[d]==distb[d]){
		int divds, divdd;
		divds = find(s);
		divdd = find(d);
		if(divds > divdd) ans--;
	}
	
	printf("%d\n", max(ans, -1));
	return 0;
}

Compilation message

007.cpp: In function 'int main()':
007.cpp:106:35: warning: self-comparison always evaluates to true [-Wtautological-compare]
  106 |  if(dista[s]==distb[s] && distb[d]==distb[d]){
      |                           ~~~~~~~~^~~~~~~~~~
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
20.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 361 ms 78684 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 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 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Execution timed out 1095 ms 315688 KB Time limit exceeded

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2888 KB Output is correct
2 Correct 30 ms 4256 KB Output is correct
3 Correct 21 ms 3016 KB Output is correct
4 Correct 25 ms 4368 KB Output is correct
5 Correct 19 ms 2760 KB Output is correct
6 Correct 17 ms 3120 KB Output is correct
7 Correct 21 ms 3272 KB Output is correct
8 Correct 21 ms 3272 KB Output is correct
9 Execution timed out 1105 ms 339724 KB Time limit exceeded
10 Execution timed out 1035 ms 524288 KB Time limit exceeded
11 Correct 52 ms 6192 KB Output is correct
12 Correct 65 ms 7668 KB Output is correct
13 Correct 49 ms 6644 KB Output is correct
14 Correct 40 ms 5712 KB Output is correct
15 Correct 58 ms 7836 KB Output is correct
16 Correct 58 ms 8176 KB Output is correct
17 Correct 57 ms 7292 KB Output is correct
18 Correct 59 ms 7288 KB Output is correct
19 Execution timed out 1094 ms 345652 KB Time limit exceeded
20 Execution timed out 1096 ms 416356 KB Time limit exceeded
21 Correct 88 ms 11140 KB Output is correct
22 Correct 76 ms 9228 KB Output is correct
23 Correct 79 ms 10408 KB Output is correct
24 Correct 78 ms 10636 KB Output is correct
25 Correct 81 ms 9884 KB Output is correct
26 Correct 67 ms 9316 KB Output is correct
27 Correct 86 ms 10540 KB Output is correct
28 Correct 76 ms 10592 KB Output is correct
29 Execution timed out 1104 ms 376696 KB Time limit exceeded
30 Execution timed out 1094 ms 395012 KB Time limit exceeded
31 Correct 103 ms 12720 KB Output is correct
32 Correct 88 ms 10540 KB Output is correct
33 Correct 91 ms 10848 KB Output is correct
34 Correct 99 ms 11328 KB Output is correct
35 Correct 83 ms 11632 KB Output is correct
36 Correct 93 ms 11968 KB Output is correct
37 Correct 103 ms 12676 KB Output is correct
38 Correct 98 ms 12452 KB Output is correct
39 Correct 108 ms 12496 KB Output is correct
40 Execution timed out 1091 ms 331488 KB Time limit exceeded
41 Execution timed out 1097 ms 374320 KB Time limit exceeded