제출 #209746

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
209746		kapsel	새로운 문제 (POI13_mor)	C++14	30 / 100	798 ms	131076 KiB

mor

#include <bits/stdc++.h>
 
using namespace std;
 
#define LL long long 
#define ULL unsigned long long 
#define LD long double 

const int INF = 1e9 + 2137;
const int N = 2 * (5e3 + 2137);
vector<int> V[N];
bool odw[N];
int odl[N];

int odlx[N][N][2];

void czysc(int n) {
	for(int i=1; i<=2*n; i++) {
		odw[i] = 0;
		odl[i] = INF;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m, q;
	cin>>n>>m>>q;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			odlx[i][j][0] = -1;
			odlx[i][j][1] = -1;
		}
	}
	int a, b, c;
	for(int i=0; i<m; i++) {
		cin>>a>>b;
		V[2*a].push_back(2*b+1);
		V[2*b].push_back(2*a+1);
		V[2*a+1].push_back(2*b);
		V[2*b+1].push_back(2*a);
	}
	for(int i=1; i<=n; i++) {
		czysc(n+4);
		queue<int> Q;
		Q.push(2*i);
		odl[2*i] = 0;
		while(!Q.empty()) {
			int v = Q.front();
			Q.pop();
			//odw[v] = 1;
			int nn = V[v].size();
			for(int j=0; j<nn; j++) {
				int u = V[v][j];
				if(!odw[u]) {
					odl[u] = odl[v] + 1;
					odw[u] = 1;
					Q.push(u);
				}
			}
		}
		for(int j=1; j<=n; j++) {
			odlx[i][j][0] = odl[2*j];
			odlx[i][j][1] = odl[2*j+1];
		}
	}
	for(int i=0; i<q; i++) {
		cin>>a>>b>>c;
		//cout<<odlx[a][b][c%2]<<endl;
		if(odlx[a][b][c%2]<=c)
			cout<<"TAK\n";
		else
			cout<<"NIE\n";
	}
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10