Submission #520374

#	Time	Username	Problem	Language	Result	Execution time	Memory
520374		Alex_tz307	Kutije (COCI21_kutije)	C++17	70 / 70	188 ms	31984 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int kN = 1e3;
const int kQ = 5e5;
vector<int> g[1 + kN], gt[1 + kN], ctc[1 + kN], t[1 + kN];
pair<int, int> edges[kN * kN];
vector<pair<int, int>> queries[1 + kN];
int ctcCnt, ctcIndex[1 + kN];
bitset<1 + kN> vis, inStack;
stack<int> st;
bitset<1 + kQ> sol;

void dfs1(int u) {
  vis[u] = true;
  for (int v : g[u]) {
    if (!vis[v]) {
      dfs1(v);
    }
  }
  st.emplace(u);
}

void dfs2(int u) {
  ctcIndex[u] = ctcCnt;
  ctc[ctcCnt].emplace_back(u);
  for (int v : gt[u]) {
    if (ctcIndex[v] == 0) {
      dfs2(v);
    }
  }
}

void dfs3(int u) {
  vis[u] = true;
  for (int v : ctc[u]) {
    inStack[v] = true;
  }
  for (int v : ctc[u]) {
    for (auto it : queries[v]) {
      sol[it.second] = inStack[it.first];
    }
  }
  for (int v : t[u]) {
    if (!vis[v]) {
      dfs3(v);
    }
  }
  for (int v : ctc[u]) {
    inStack[v] = false;
  }
}

void TestCase() {
  int n, m, q;
  cin >> n >> m >> q;
  int cntE = 0;
  for (int i = 1; i <= m; ++i) {
    for (int u = 1; u <= n; ++u) {
      int v;
      cin >> v;
      g[u].emplace_back(v);
      gt[v].emplace_back(u);
      edges[cntE++] = {u, v};
    }
  }
  for (int i = 1; i <= q; ++i) {
    int u, v;
    cin >> u >> v;
    queries[v].emplace_back(u, i);
  }
  for (int v = 1; v <= n; ++v) {
    if (!vis[v]) {
      dfs1(v);
    }
  }
  while (!st.empty()) {
    int u = st.top();
    st.pop();
    if (ctcIndex[u] == 0) {
      ++ctcCnt;
      dfs2(u);
    }
  }
  for (int i = 0; i < n * m; ++i) {
    int u, v;
    tie(u, v) = edges[i];
    int p = ctcIndex[u], r = ctcIndex[v];
    if (p != r) {
      t[p].emplace_back(r);
    }
  }
  vis.reset();
  for (int i = 1; i <= ctcCnt; ++i) {
    if (!vis[i]) {
      dfs3(i);
    }
  }
  for (int i = 1; i <= q; ++i) {
    if (sol[i]) {
      cout << "DA\n";
    } else {
      cout << "NE\n";
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 1; tc <= tests; ++tc) {
    TestCase();
  }
  return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 35 / 35