oj.uz

답안 #106308

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106308 2019-04-17T20:41:49 Z xiaowuc1 Tales of seafaring (POI13_mor) C++14
100 / 100
 2071 ms 102616 KB 
#include <algorithm>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> plli;
typedef vector<vector<ll>> matrix;

vector<int> edges[5000];
short dp[5000][5000][2];
int n;

const short INF = 30000;

void init() {
  for(int s = 0; s < n; s++) {
    for(int t = 0; t < n; t++) {
      dp[s][t][0] = INF;
      dp[s][t][1] = INF;
    }
    queue<int> q;
    for(int out: edges[s]) {
      dp[s][out][1] = 1;
      q.push(out);
    }
    while(!q.empty()) {
      int t = q.front();
      q.pop();
      for(int out: edges[t]) {
        bool upd = false;
        if(dp[s][out][1] > dp[s][t][0] + 1) {
          dp[s][out][1] = dp[s][t][0] + 1;
          upd = true;
        }
        if(dp[s][out][0] > dp[s][t][1] + 1) {
          dp[s][out][0] = dp[s][t][1] + 1;
          upd = true;
        }
        if(upd) q.push(out);
      }
    }
  }
}

void solve() {
  int m, q;
  cin >> n >> m >> q;
  while(m--) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    edges[a].push_back(b);
    edges[b].push_back(a);
  }
  init();
  while(q--) {
    int a, b, w;
    cin >> a >> b >> w;
    a--;
    b--;
    if(dp[a][b][w%2] == INF) cout << "NIE\n";
    else if(dp[a][b][w%2] <= w) cout << "TAK\n";
    else cout << "NIE\n";
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
	/*
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
	*/
	solve();
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 358 ms 20316 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 277 ms 20216 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 2688 KB Output is correct
2 Correct 4 ms 1408 KB Output is correct
3 Correct 18 ms 3456 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 4344 KB Output is correct
2 Correct 15 ms 6272 KB Output is correct
3 Correct 50 ms 6264 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 126 ms 15352 KB Output is correct
2 Correct 13 ms 5696 KB Output is correct
3 Correct 262 ms 24256 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 757 ms 28224 KB Output is correct
2 Correct 35 ms 24188 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1488 ms 83004 KB Output is correct
2 Correct 108 ms 24952 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1624 ms 102548 KB Output is correct
2 Correct 327 ms 97272 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2071 ms 102616 KB Output is correct
2 Correct 569 ms 93760 KB Output is correct