oj.uz

Submission #165231

# Submission time Handle Problem Language Result Execution time Memory
165231 2019-11-26T06:56:01 Z Lightning Tales of seafaring (POI13_mor) C++14
100 / 100
 2445 ms 117884 KB 
#include <iostream>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef pair <short int, short int> pii;

#define sz(a) (int)a.size()
#define mkp make_pair
#define pb emplace_back

const short N = 5003;
const short INF = 30000;

short n, m;
int k;
short dOdd[N], dEven[N];
vector <short> g[N];
//map <pii, int> mnDistOdd, mnDistEven;
short mnDistOdd[N][N], mnDistEven[N][N];
queue <short> q;

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m >> k;
	for(short i = 1; i <= m; ++i) {
		short a, b;
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
	}
	for(short cur = 1; cur <= n; ++cur) {
		for(short i = 1; i <= n; ++i) {
			dOdd[i] = INF;
			dEven[i] = INF;	
		}
		dEven[cur] = 0;
		q.push(cur);
		while(sz(q)) {
			short v = q.front();
			q.pop();
			for(short to : g[v]) {
				bool add = 0;
				if(dOdd[to] > dEven[v] + 1) {
					dOdd[to] = dEven[v] + 1;
					add = 1;
				}
				if(dEven[to] > dOdd[v] + 1) {
					dEven[to] = dOdd[v] + 1;
					add = 1;
				}				
				if(add) {
					q.push(to);
				}
			}				
		}
		for(short i = 1; i <= n; ++i) {
			mnDistOdd[cur][i] = dOdd[i];
			mnDistEven[cur][i] = dEven[i];
		}
	}
	for(int it = 1; it <= k; ++it) {
		short a, b;
		int dist;
		cin >> a >> b >> dist;	
		if(!sz(g[a]) || !sz(g[b])) {
			cout << "NIE\n";
			continue;
		}
		if(dist & 1) {
			if(mnDistOdd[a][b] <= dist && mnDistOdd[a][b] != INF) {
				cout << "TAK\n";
			} else {
				cout << "NIE\n";
			}			
		} else {
			if(mnDistEven[a][b] <= dist && mnDistEven[a][b] != INF) {
				cout << "TAK\n";
			} else {
				cout << "NIE\n";
			}
		}
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 350 ms 20732 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 636 KB Output is correct
4 Correct 361 ms 20792 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4348 KB Output is correct
2 Correct 5 ms 2168 KB Output is correct
3 Correct 22 ms 5544 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 6904 KB Output is correct
2 Correct 20 ms 9592 KB Output is correct
3 Correct 59 ms 9640 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 21676 KB Output is correct
2 Correct 20 ms 8824 KB Output is correct
3 Correct 310 ms 32496 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 837 ms 50116 KB Output is correct
2 Correct 54 ms 32376 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1710 ms 96492 KB Output is correct
2 Correct 143 ms 35576 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1963 ms 117884 KB Output is correct
2 Correct 381 ms 101228 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2445 ms 117692 KB Output is correct
2 Correct 709 ms 105144 KB Output is correct