Submission #165231

#	Time	Username	Problem	Language	Result	Execution time	Memory
165231		Lightning	Tales of seafaring (POI13_mor)	C++14	100 / 100	2445 ms	117884 KiB

mor

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10