oj.uz

Submission #30572

# Submission time Handle Problem Language Result Execution time Memory
30572 2017-07-25T02:18:33 Z sampriti File Paths (BOI15_fil) C++14
33 / 100
 119 ms 3624 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

vector<int> T[3001];
int dir_par[3001], dir_len[3001];
bool sieve[1000001];
int D[3001];
set<int> D_set;
int file_par[3001], file_len[3001];
bool ans[3001];
vector<int> files_by_dir[3001];

void dfs_dist(int i, int d) {
  d += dir_len[i];
  D[i] = d;

  for(int u: T[i]) {
    dfs_dist(u, d);
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(0);

  int N, M, K; cin >> N >> M >> K;
  int S; cin >> S; S++;

  dir_par[0] = -1; dir_len[0] = 1;
  for(int i = 1; i <= N; i++) {
    cin >> dir_par[i] >> dir_len[i];
    dir_len[i]++;
    T[dir_par[i]].push_back(i);
  }

  for(int i = 1; i <= M; i++) {
    cin >> file_par[i] >> file_len[i];
  }

  dfs_dist(0, 0);
  for(int i = 0; i <= N; i++) D_set.insert(D[i]);

  for(int i = 1; i <= M; i++) {
    int req = K - file_len[i];

    if(D[file_par[i]] == req) {
      ans[i] = true;
      continue;
    }

    int j = file_par[i], len = 0;
    while(j != -1) {
      if(D_set.count(req - len - S)) {
        ans[i] = true;
        break;
      }
      len += dir_len[j];
      j = dir_par[j];
    }
  }

  for(int i = 1; i <= M; i++) {
    files_by_dir[file_par[i]].push_back(i);
  }

  for(int i = 1; i <= M; i++) {
    if(ans[i]) cout << "YES" << endl;
    else cout << "NO" << endl;
  }
}

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 3360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3492 KB Output is correct
2 Correct 6 ms 3492 KB Output is correct
3 Correct 3 ms 3492 KB Output is correct
4 Correct 3 ms 3492 KB Output is correct
5 Correct 66 ms 3624 KB Output is correct
6 Correct 76 ms 3624 KB Output is correct
7 Correct 56 ms 3624 KB Output is correct
8 Correct 49 ms 3624 KB Output is correct
9 Correct 3 ms 3492 KB Output is correct
10 Correct 9 ms 3492 KB Output is correct
11 Correct 6 ms 3492 KB Output is correct
12 Correct 119 ms 3624 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 3360 KB Output isn't correct
2 Halted 0 ms 0 KB -