oj.uz

Submission #101125

# Submission time Handle Problem Language Result Execution time Memory
101125 2019-03-16T18:10:15 Z Bruteforceman 007 (CEOI14_007) C++11
46.3333 / 100
 253 ms 30044 KB 
#include "bits/stdc++.h"
using namespace std;
int d[4][100010];
vector <int> g[100010];

void bfs(int src, int r) {
	queue <int> Q;
	Q.push(src);
	d[r][src] = 0;
	while(!Q.empty()) {
		int x = Q.front();
		Q.pop();
		for(auto i : g[x]) {
			if(d[r][i] == -1) {
				d[r][i] = d[r][x] + 1;
				Q.push(i);
			}		
		}
	}
}

int dp[100010], fn[100010];
typedef pair <int, int> pii;

int main(int argc, char const *argv[])
{
	int n, m;
	scanf("%d %d", &n, &m);
	int s, t, a, b;
	scanf("%d %d %d %d", &s, &t, &a, &b);
	for(int i = 1; i <= m; i++) {
		int p, q;
		scanf("%d %d", &p, &q);
		g[p].emplace_back(q);
		g[q].emplace_back(p);
	}
	memset(d, -1, sizeof d);
	bfs(s, 0);
	bfs(t, 1);
	if(d[1][a] > d[1][b]) swap(a, b);
	if(d[1][a] == d[1][b] && d[0][a] < d[0][b]) swap(a, b);
	bfs(a, 2);
	bfs(b, 3);

	int opt = d[1][a] - d[0][a];

	if(d[1][a] < d[0][a] || d[1][b] < d[0][b]) {
		printf("-1\n");
		exit(0);
	}
	if(d[1][a] != d[1][b] && d[0][a] != d[0][b]) {
		printf("%d\n", opt);
		exit(0);
	}
	vector <pii> v;
	for(int i = 1; i <= n; i++) {
		v.emplace_back(-d[0][i], i);
	}
	sort(v.begin(), v.end());

	for(int i = 0; i < v.size(); i++) {
		int x = v[i].second;
		for(int j : g[x]) {
			if(d[0][j] <= d[0][x]) continue;
			if(d[2][j] + d[0][j] == d[0][a] && d[3][j] + d[0][j] == d[0][b]) {
				dp[x] = max(dp[x], 1 + dp[j]);
			}
		}
	}
	v.clear();
	
	for(int i = 1; i <= n; i++) {
		v.emplace_back(-d[1][i], i);
	}
	sort(v.begin(), v.end());
	for(int i = 0; i < v.size(); i++) {
		int x = v[i].second;
		for(int j : g[x]) {
			if(d[1][j] <= d[1][x]) continue;
			if(d[2][j] + d[1][j] == d[1][a] && d[3][j] + d[1][j] == d[1][b]) {
				fn[x] = max(fn[x], 1 + fn[j]);
			}
		}
	}
	if(dp[s] < fn[t] - opt) {
		printf("%d\n", opt - 1);
	} else {
		printf("%d\n", opt);
	}
	return 0;
}

Compilation message

007.cpp: In function 'int main(int, const char**)':
007.cpp:61:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size(); i++) {
                 ~~^~~~~~~~~~
007.cpp:76:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size(); i++) {
                 ~~^~~~~~~~~~
007.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
007.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d", &s, &t, &a, &b);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &p, &q);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
23.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4224 KB Output is correct
2 Correct 6 ms 4224 KB Output is correct
3 Correct 7 ms 4196 KB Output is correct
4 Correct 6 ms 4224 KB Output is correct
5 Correct 3 ms 4224 KB Output is correct
6 Correct 6 ms 4224 KB Output is correct
7 Correct 6 ms 4224 KB Output is correct
8 Correct 7 ms 4268 KB Output is correct
9 Correct 7 ms 4224 KB Output is correct
10 Correct 7 ms 4224 KB Output is correct
11 Partially correct 6 ms 4224 KB Partially correct
12 Correct 7 ms 4224 KB Output is correct
13 Correct 6 ms 4224 KB Output is correct
14 Correct 6 ms 4224 KB Output is correct
15 Correct 6 ms 4224 KB Output is correct
16 Correct 7 ms 4224 KB Output is correct
17 Correct 6 ms 4352 KB Output is correct
18 Correct 7 ms 4224 KB Output is correct
19 Correct 6 ms 4352 KB Output is correct
20 Correct 7 ms 4224 KB Output is correct
21 Correct 7 ms 4224 KB Output is correct
22 Correct 8 ms 4224 KB Output is correct
23 Correct 6 ms 4224 KB Output is correct
24 Correct 9 ms 4352 KB Output is correct

Subtask #2
23.333333 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 6820 KB Output is correct
2 Correct 68 ms 7800 KB Output is correct
3 Correct 51 ms 6896 KB Output is correct
4 Correct 73 ms 8052 KB Output is correct
5 Correct 35 ms 5888 KB Output is correct
6 Correct 37 ms 6108 KB Output is correct
7 Correct 59 ms 7032 KB Output is correct
8 Correct 52 ms 7032 KB Output is correct
9 Correct 79 ms 8176 KB Output is correct
10 Correct 248 ms 16728 KB Output is correct
11 Correct 108 ms 9712 KB Output is correct
12 Runtime error 74 ms 16872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Correct 162 ms 10196 KB Output is correct
14 Correct 69 ms 7800 KB Output is correct
15 Runtime error 72 ms 17016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 73 ms 17400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 96 ms 18400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 81 ms 16452 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 114 ms 20028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 241 ms 28552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 142 ms 20388 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 87 ms 18748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 136 ms 20140 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 97 ms 20124 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 93 ms 19452 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 81 ms 18808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 96 ms 20344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 109 ms 20440 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 226 ms 23288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 253 ms 30044 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 10 ms 5248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 102 ms 20300 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 100 ms 20600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 9 ms 5504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 100 ms 20820 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 8 ms 5248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 9 ms 5120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 10 ms 5152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 7 ms 5120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 9 ms 5248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 8 ms 5220 KB Execution killed with signal 11 (could be triggered by violating memory limits)