Submission #1267975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267975		rtri	File Paths (BOI15_fil)	C++20	0 / 100	1093 ms	840 KiB

fil

#include <bits/stdc++.h>
using namespace std;

int n, m, k, s, nodes;
vector<vector<int>> adj;
vector<int> namelen;
vector<int> preflen;
vector<int> par;
vector<int> tin, tout;

int timer = 0;
void dfs(int u, int len, int p = -1) {
  len += namelen[u];
  if (u <= n)
    len++;
  preflen[u] = len;

  tin[u] = timer++;
  for (int v : adj[u])
    if (v != p)
      dfs(v, len, u);
  tout[u] = timer++;
}

bool anc(int u, int anc) { return tin[anc] < tin[u] && tout[u] < tout[anc]; }

int main() {
  cin >> n >> m >> k >> s;
  nodes = n + 1 + m;

  adj.resize(nodes);
  namelen.resize(nodes);
  par.resize(nodes);

  namelen[0] = 0;
  par[0] = -1;

  for (int i = 1; i <= n; i++) {
    int p, l;
    cin >> p >> l;
    adj[i].push_back(p);
    adj[p].push_back(i);
    par[i] = p;
    namelen[i] = l;
  }

  for (int i = 0; i < m; i++) {
    int p, l;
    cin >> p >> l;
    adj[i + n + 1].push_back(p);
    adj[p].push_back(i + n + 1);
    namelen[i + n + 1] = l;
    par[i + n + 1] = p;
  }

  tin.resize(nodes);
  tout.resize(nodes);
  preflen.resize(nodes);
  dfs(0, 0);

  vector<bool> ans(m);
  for (int i = 0; i < m; i++) {
    int file = i + n + 1;
    if (preflen[file] == k)
      ans[i] = 1;
    else if (k < preflen[file])
      ans[i] = 0;
    else {
      int symend = file;
      bool is_possible = 0;
      while (symend != -1) {
        for (int symstart = 0; symstart <= n; symstart++) {
          if (anc(symstart, symend)) {
            is_possible |=
                0 == (k - preflen[file]) %
                         (s + 1 + preflen[symstart] - preflen[symend]);
          } else {
            is_possible |= k == s + 1 + preflen[file] -
                                    (symend == 0 ? 0 : preflen[par[symend]]) +
                                    preflen[symstart];
          }
        }

        symend = par[symend];
      }
      ans[i] = is_possible;
    }
  }

  for (bool a : ans)
    if (a)
      cout << "YES\n";
    else
      cout << "NO\n";
  cout << flush;

  return 0;
}

• Subtask 1: 0 / 33
• Subtask 2: 0 / 33
• Subtask 3: 0 / 34