oj.uz

답안 #209746

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
209746 2020-03-15T13:06:47 Z kapsel Tales of seafaring (POI13_mor) C++14
30 / 100
 798 ms 131076 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 632 KB Output is correct
2 Incorrect 5 ms 632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Incorrect 5 ms 760 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1016 KB Output is correct
2 Correct 5 ms 888 KB Output is correct
3 Correct 5 ms 888 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 3704 KB Output is correct
2 Correct 7 ms 1784 KB Output is correct
3 Correct 25 ms 4856 KB Output is correct

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 6264 KB Output is correct
2 Correct 21 ms 9336 KB Output is correct
3 Incorrect 64 ms 9336 KB Output isn't correct

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 25092 KB Output is correct
2 Correct 21 ms 8312 KB Output is correct
3 Incorrect 347 ms 40800 KB Output isn't correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 798 ms 58488 KB Output is correct
2 Correct 58 ms 40568 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 85 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 76 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 77 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -