oj.uz

Submission #261673

# Submission time Handle Problem Language Result Execution time Memory
261673 2020-08-12T00:17:50 Z rama_pang Viruses (BOI20_viruses) C++14
100 / 100
 119 ms 4472 KB 
#include <bits/stdc++.h>
using namespace std;

class AhoCorasick {
 public:
  int sz;
  vector<int> sl; // suffix link
  vector<int> bad; // bad prefixes
  vector<array<int, 2>> d; // transition
  vector<array<int, 2>> c; // trie

  AhoCorasick() : sz(1), sl(1, 0), bad(1, 0), d(1, {0, 0}), c(1, {0, 0}) {}

  int NewNode() {
    sl.emplace_back(0);
    bad.emplace_back(0);
    d.push_back({0, 0});
    c.push_back({0, 0});
    return sz++;
  }

  void InsertString(vector<int> s) {
    int u = 0;
    for (auto i : s) {
      if (!c[u][i]) {
        int nw = NewNode();
        c[u][i] = nw;
      }
      u = c[u][i];
    }
    bad[u] = 1;
  }

  void Build() {
    for (queue<int> q({0}); !q.empty(); q.pop()) {
      int u = q.front();
      bad[u] |= bad[sl[u]];
      for (int i = 0; i < 2; i++) {
        int v = c[u][i];
        if (v != 0) {
          sl[v] = d[sl[u]][i];
          d[u][i] = v;
          bad[v] |= bad[u];
          q.emplace(v);
        } else {
          d[u][i] = d[sl[u]][i];
        }
      }
    }
  }

  bool IsBadPrefix(int x) {
    return bad[x];
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  
  int G, N, M;
  cin >> G >> N >> M;

  vector<vector<vector<int>>> adj(G);
  for (int rep = 0; rep < N; rep++) {
    int u, k;
    cin >> u >> k;
    vector<int> v;
    while (k--) {
      v.emplace_back();
      cin >> v.back();
    }
    while ((int) v.size() > 2) {
      int v2 = v.back(); v.pop_back();
      int v1 = v.back(); v.pop_back();
      int new_node = (int) adj.size();
      adj.emplace_back();
      adj[new_node].emplace_back();
      adj[new_node].back().emplace_back(v1);
      adj[new_node].back().emplace_back(v2);
      v.emplace_back(new_node);
    }
    adj[u].emplace_back();
    for (auto vi : v) {
      adj[u].back().emplace_back(vi);
    }
  }

  vector<vector<pair<int, int>>> radj(adj.size());
  for (int u = 0; u < (int) adj.size(); u++) {
    for (int vid = 0; vid < (int) adj[u].size(); vid++) {
      for (auto v : adj[u][vid]) {
        radj[v].emplace_back(u, vid);
      }
    }
  }

  AhoCorasick ac;
  for (int rep = 0; rep < M; rep++) {
    int l;
    cin >> l;
    vector<int> s;
    while (l--) {
      s.emplace_back();
      cin >> s.back();
    }
    ac.InsertString(s);
  }
  ac.Build();

  const unsigned long long INF = 1ull << 63;
  vector<vector<vector<unsigned long long>>> dist(adj.size(), 
      vector<vector<unsigned long long>>(ac.sz, vector<unsigned long long>(ac.sz, INF)));

  struct State {
    int u, st, et;
    unsigned long long d;
    State() {}
    State(int u, int st, int et, unsigned long long d) : u(u), st(st), et(et), d(d) {}
    const bool operator < (const State &o) const { return d > o.d; }
  };

  priority_queue<State> pq;
  auto Relax = [&](int x, int y, int z, unsigned long long w) {
    if (!ac.IsBadPrefix(y) && !ac.IsBadPrefix(z) && dist[x][y][z] > w) {
      dist[x][y][z] = w;
      pq.emplace(x, y, z, w);
    }
  };

  // Base Case
  for (int st = 0; st < ac.sz; st++) {
    Relax(0, st, ac.d[st][0], 1);
    Relax(1, st, ac.d[st][1], 1);
  }
  
  // Dijkstra
  while (!pq.empty()) {
    State s = pq.top();
    pq.pop();
    if (dist[s.u][s.st][s.et] != s.d || dist[s.u][s.st][s.et] == INF) {
      continue;
    }
    for (auto r : radj[s.u]) {
      int par = r.first;
      int id = r.second;
      if ((int) adj[par][id].size() == 1) {
        Relax(par, s.st, s.et, dist[s.u][s.st][s.et]);
      }
      if ((int) adj[par][id].size() == 2 && adj[par][id][0] == s.u) {
        int v = adj[par][id][1];
        for (int i = 0; i < ac.sz; i++) {
          Relax(par, s.st, i, dist[s.u][s.st][s.et] + dist[v][s.et][i]);
        }
      }
      if ((int) adj[par][id].size() == 2 && adj[par][id][1] == s.u) {
        int v = adj[par][id][0];
        for (int i = 0; i < ac.sz; i++) {
          Relax(par, i, s.et, dist[v][i][s.st] + dist[s.u][s.st][s.et]);
        }
      }
    }
  }

  for (int i = 2; i < G; i++) {
    unsigned long long ans = INF;
    for (int j = 0; j < ac.sz; j++) {
      if (!ac.IsBadPrefix(j) && ans > dist[i][0][j]) {
        ans = dist[i][0][j];
      }
    }
    if (ans == INF) {
      cout << "YES\n";
    } else {
      cout << "NO " << ans << "\n";
    }
  }
  return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 1536 KB Output is correct
4 Correct 2 ms 2560 KB Output is correct
5 Correct 3 ms 1536 KB Output is correct
6 Correct 3 ms 1408 KB Output is correct
7 Correct 3 ms 1792 KB Output is correct
8 Correct 3 ms 1920 KB Output is correct
9 Correct 2 ms 1280 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 768 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 1 ms 1024 KB Output is correct
14 Correct 1 ms 640 KB Output is correct
15 Correct 1 ms 768 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 768 KB Output is correct
18 Correct 1 ms 768 KB Output is correct
19 Correct 1 ms 768 KB Output is correct
20 Correct 1 ms 768 KB Output is correct
21 Correct 1 ms 768 KB Output is correct
22 Correct 1 ms 512 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 0 ms 384 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1536 KB Output is correct
2 Correct 2 ms 2560 KB Output is correct
3 Correct 3 ms 1536 KB Output is correct
4 Correct 3 ms 1408 KB Output is correct
5 Correct 3 ms 1792 KB Output is correct
6 Correct 3 ms 1920 KB Output is correct
7 Correct 2 ms 1280 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 512 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 0 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 9 ms 1280 KB Output is correct
26 Correct 1 ms 1408 KB Output is correct
27 Correct 113 ms 1792 KB Output is correct
28 Correct 5 ms 1920 KB Output is correct
29 Correct 119 ms 4468 KB Output is correct
30 Correct 115 ms 4472 KB Output is correct
31 Correct 9 ms 1920 KB Output is correct
32 Correct 5 ms 1920 KB Output is correct
33 Correct 4 ms 1408 KB Output is correct
34 Correct 109 ms 2944 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 512 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 0 ms 384 KB Output is correct
34 Correct 1 ms 384 KB Output is correct
35 Correct 0 ms 384 KB Output is correct
36 Correct 1 ms 384 KB Output is correct
37 Correct 1 ms 384 KB Output is correct
38 Correct 1 ms 384 KB Output is correct
39 Correct 1 ms 384 KB Output is correct
40 Correct 1 ms 384 KB Output is correct
41 Correct 1 ms 384 KB Output is correct
42 Correct 1 ms 384 KB Output is correct
43 Correct 1 ms 384 KB Output is correct
44 Correct 1 ms 384 KB Output is correct
45 Correct 1 ms 512 KB Output is correct
46 Correct 1 ms 384 KB Output is correct
47 Correct 1 ms 384 KB Output is correct
48 Correct 1 ms 512 KB Output is correct
49 Correct 1 ms 384 KB Output is correct
50 Correct 1 ms 384 KB Output is correct
51 Correct 1 ms 384 KB Output is correct
52 Correct 1 ms 384 KB Output is correct
53 Correct 1 ms 384 KB Output is correct
54 Correct 1 ms 384 KB Output is correct
55 Correct 1 ms 384 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 2 ms 1536 KB Output is correct
22 Correct 2 ms 2560 KB Output is correct
23 Correct 3 ms 1536 KB Output is correct
24 Correct 3 ms 1408 KB Output is correct
25 Correct 3 ms 1792 KB Output is correct
26 Correct 3 ms 1920 KB Output is correct
27 Correct 2 ms 1280 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 1 ms 768 KB Output is correct
30 Correct 1 ms 512 KB Output is correct
31 Correct 1 ms 1024 KB Output is correct
32 Correct 1 ms 640 KB Output is correct
33 Correct 1 ms 768 KB Output is correct
34 Correct 1 ms 384 KB Output is correct
35 Correct 1 ms 768 KB Output is correct
36 Correct 1 ms 768 KB Output is correct
37 Correct 1 ms 768 KB Output is correct
38 Correct 1 ms 768 KB Output is correct
39 Correct 1 ms 768 KB Output is correct
40 Correct 1 ms 512 KB Output is correct
41 Correct 1 ms 384 KB Output is correct
42 Correct 0 ms 384 KB Output is correct
43 Correct 1 ms 384 KB Output is correct
44 Correct 1 ms 384 KB Output is correct
45 Correct 1 ms 384 KB Output is correct
46 Correct 1 ms 384 KB Output is correct
47 Correct 1 ms 384 KB Output is correct
48 Correct 1 ms 384 KB Output is correct
49 Correct 1 ms 384 KB Output is correct
50 Correct 1 ms 384 KB Output is correct
51 Correct 1 ms 384 KB Output is correct
52 Correct 1 ms 512 KB Output is correct
53 Correct 1 ms 384 KB Output is correct
54 Correct 0 ms 384 KB Output is correct
55 Correct 1 ms 384 KB Output is correct
56 Correct 0 ms 384 KB Output is correct
57 Correct 1 ms 384 KB Output is correct
58 Correct 1 ms 384 KB Output is correct
59 Correct 1 ms 384 KB Output is correct
60 Correct 9 ms 1280 KB Output is correct
61 Correct 1 ms 1408 KB Output is correct
62 Correct 113 ms 1792 KB Output is correct
63 Correct 5 ms 1920 KB Output is correct
64 Correct 119 ms 4468 KB Output is correct
65 Correct 115 ms 4472 KB Output is correct
66 Correct 9 ms 1920 KB Output is correct
67 Correct 5 ms 1920 KB Output is correct
68 Correct 4 ms 1408 KB Output is correct
69 Correct 109 ms 2944 KB Output is correct
70 Correct 1 ms 384 KB Output is correct
71 Correct 1 ms 384 KB Output is correct
72 Correct 1 ms 384 KB Output is correct
73 Correct 1 ms 384 KB Output is correct
74 Correct 1 ms 384 KB Output is correct
75 Correct 1 ms 384 KB Output is correct
76 Correct 1 ms 512 KB Output is correct
77 Correct 1 ms 384 KB Output is correct
78 Correct 1 ms 384 KB Output is correct
79 Correct 1 ms 512 KB Output is correct
80 Correct 1 ms 384 KB Output is correct
81 Correct 1 ms 384 KB Output is correct
82 Correct 1 ms 384 KB Output is correct
83 Correct 1 ms 384 KB Output is correct
84 Correct 1 ms 384 KB Output is correct
85 Correct 1 ms 384 KB Output is correct
86 Correct 1 ms 384 KB Output is correct
87 Correct 13 ms 896 KB Output is correct
88 Correct 1 ms 384 KB Output is correct
89 Correct 1 ms 384 KB Output is correct
90 Correct 1 ms 640 KB Output is correct
91 Correct 1 ms 512 KB Output is correct
92 Correct 29 ms 1920 KB Output is correct
93 Correct 21 ms 1792 KB Output is correct
94 Correct 1 ms 1024 KB Output is correct
95 Correct 1 ms 768 KB Output is correct
96 Correct 1 ms 896 KB Output is correct
97 Correct 7 ms 1152 KB Output is correct
98 Correct 2 ms 1152 KB Output is correct
99 Correct 11 ms 1664 KB Output is correct
100 Correct 2 ms 1024 KB Output is correct
101 Correct 3 ms 896 KB Output is correct
102 Correct 74 ms 3068 KB Output is correct
103 Correct 5 ms 1536 KB Output is correct
104 Correct 17 ms 1664 KB Output is correct
105 Correct 1 ms 512 KB Output is correct
106 Correct 27 ms 2056 KB Output is correct
107 Correct 26 ms 2056 KB Output is correct