oj.uz

Submission #369872

# Submission time Handle Problem Language Result Execution time Memory
369872 2021-02-22T16:43:10 Z AA_Surely Tales of seafaring (POI13_mor) C++14
60 / 100
 3000 ms 131076 KB 
#include <bits/stdc++.h>

#define FOR(i,x,n) for(int i=x; i<n; i++)
#define F0R(i,n) FOR(i,0,n)
#define ROF(i,x,n) for(int i=n-1; i>=x; i--)
#define R0F(i,n) ROF(i,0,n)
 
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define F first
#define S second
#define pb push_back
#define mp make_pair

#define FILL(a, b) memset(a, b, sizeof(a));

using namespace std;
typedef long long LL;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

typedef vector<int> VI;

const int MAXN = 5000+7;

LL n, m, k, u, v, to, st, fn, len;
VI adj[MAXN];
LL fastest_route[MAXN][MAXN][2];

void Input() {
	cin >>n >> m >> k;
	F0R (i, m) {
		cin >> u >> v;
		adj[--u].pb(--v);
		adj[v].pb(u);
	}
}

void Bfs(int now_on) {
	
	queue <PII> keep;
	PII add, on; add.F = now_on; add.S = 0;
	keep.push(add);
	
	while (!keep.empty()) {
		on = keep.front(); keep.pop();
		on.S++;
//		cout << "ON " << on.F + 1 << " FROM " << now_on + 1 << " WITH LENGTH " << on.S - 1 << endl;
		F0R (i, adj[on.F].size()) {
			to = adj[on.F][i];
			if (fastest_route[now_on][to][0] == 0 && on.S % 2 == 0) {
				fastest_route[now_on][to][0] = on.S;
				add.F = to; add.S = on.S; keep.push(add);
			}
			
			else if (fastest_route[now_on][to][1] == 0 && on.S % 2 == 1) {
				fastest_route[now_on][to][1] = on.S;
				add.F = to; add.S = on.S; keep.push(add);
			}
		}
	}
	
	return;
}

int main() {
	IOS;
	Input();
	F0R (i, n) Bfs(i);
	
	/*
	F0R (i, 8) {
		F0R (j, 8) cout << fastest_route[i][j][0] << "/" << fastest_route[i][j][1] << ' ';
		cout << endl;
	}
	**/
	
	F0R (i, k) {
		cin >> st >> fn >> len;
		if (fastest_route[st - 1][fn - 1][len & 1] != 0 
			&& fastest_route[st - 1][fn - 1][len & 1] <= len) {
				cout << "TAK" << endl;
			}
		else cout << "NIE" << endl;
	}
}

Compilation message

mor.cpp: In function 'void Bfs(int)':
mor.cpp:3:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i,x,n) for(int i=x; i<n; i++)
      |                                  ^
mor.cpp:4:18: note: in expansion of macro 'FOR'
    4 | #define F0R(i,n) FOR(i,0,n)
      |                  ^~~
mor.cpp:49:3: note: in expansion of macro 'F0R'
   49 |   F0R (i, adj[on.F].size()) {
      |   ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 2496 ms 20648 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 516 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 2464 ms 20604 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 748 KB Output is correct
2 Correct 2 ms 748 KB Output is correct
3 Correct 4 ms 748 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4716 KB Output is correct
2 Correct 8 ms 1804 KB Output is correct
3 Correct 31 ms 6252 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 8848 KB Output is correct
2 Correct 43 ms 13676 KB Output is correct
3 Correct 104 ms 13932 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 42352 KB Output is correct
2 Correct 32 ms 12368 KB Output is correct
3 Correct 481 ms 70252 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3010 ms 89012 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 816 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 578 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 686 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -