oj.uz

Submission #1042290

# Submission time Handle Problem Language Result Execution time Memory
1042290 2024-08-02T19:22:23 Z erray Board Game (JOI24_boardgame) C++17
100 / 100
 1984 ms 1042936 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/ioi/contests/ioi23_d2/debug.h"
#else 
  #define debug(...) void(37)
#endif

#define IWANNATEST false

using Poly = array<int64_t, 2>;
Poly operator+(Poly a, Poly b) {
  a[0] += b[0];
  a[1] += b[1];
  return a;
}
Poly& operator+=(Poly& a, Poly b) {
  a = a + b;
  return a;
}
Poly operator-(Poly a, Poly b) {
  a[0] -= b[0];
  a[1] -= b[1];
  return a;
}
int64_t eval(Poly a, int x) {
  return a[0] + 1LL * x * a[1];
}

template<typename T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

constexpr int64_t inf = int64_t(1E16);
vector<int64_t> SP(const vector<vector<array<int, 2>>>& g, vector<int> sources) {
  int n = int(g.size());
  vector<int64_t> dist(n, inf);
  min_pq<pair<int64_t, int>> pq;
  auto Add = [&](int v, int64_t d) {
    if (dist[v] > d) {
      dist[v] = d;
      pq.emplace(d, v);
    }
  };
  for (auto v : sources) Add(v, 0);
  while (!pq.empty()) {
    auto[d, v] = pq.top();
    pq.pop();
    if (dist[v] < d) continue;
    for (auto[u, w] : g[v]) {
      Add(u, d + w);
    }
  }
  for (int i = 0; i < n; ++i) if (dist[i] == inf) dist[i] = -1;
  return dist;
}
 

vector<int> BFS(vector<vector<array<int, 2>>> g, vector<int> sources) {
  for (auto l : g) for (auto[u, w] : l) assert(w == 1);
  int n = int(g.size());
  vector<int> dist(n, -1);
  vector<int> que;
  auto Add = [&](int x, int d) {
    if (dist[x] == -1) {
      dist[x] = d;
      que.push_back(x);
    }
  };
  for (auto v : sources) Add(v, 0);
  for (int it = 0; it < int(que.size()); ++it) {
    int v = que[it];
    for (auto[u, foo] : g[v]) {
      Add(u, dist[v] + 1);
    }
  }
  return dist;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N, M, K;
  cin >> N >> M >> K;
  vector<int> V(2 * M), U(2 * M);
  for (int i = 0; i < M; ++i) {
    cin >> V[i] >> U[i];
    --V[i], --U[i];
    U[i + M] = V[i];
    V[i + M] = U[i];
  }
  vector<bool> S(N);
  for (int i = 0; i < N; ++i) {
    char C;
    cin >> C;
    S[i] = (C == '1');
  }
  vector<int> X(K);
  for (int i = 0; i < K; ++i) {
    cin >> X[i];
    --X[i];
  }
  int Z = X[0];
  --K;
  X.erase(X.begin());
  debug(Z, X);
  vector<bool> two_source(N);
  bool two_found = false;
  for (int i = 0; i < M; ++i) {
    if (S[V[i]] && S[U[i]]) {
      two_source[V[i]] = two_source[U[i]] = true;
      two_found = true;
    }
  }
  debug(two_source);
  bool all_zero = count(S.begin(), S.end(), true) == 0;
  vector<int> single_d(N);
  if (!all_zero) {
    vector<vector<array<int, 2>>> g(N);
    for (int i = 0; i < 2 * M; ++i) {
      g[V[i]].push_back({U[i], 1});
    }
    vector<int> sources;
    for (int i = 0; i < N; ++i) {
      if (S[i]) sources.push_back(i);
    }
    auto foo = SP(g, sources);
    for (int i = 0; i < N; ++i) {
      if (foo[i] == 0) {
        single_d[i] = 0;
      } else {
        single_d[i] = int(foo[i] - 2);
      }
    }
  } else {
    single_d.assign(N, N + 1);
  }
  vector<int> two_d(N);
  if (two_found) {
    vector<vector<array<int, 2>>> g(N);
    for (int i = 0; i < 2 * M; ++i) {
      g[V[i]].push_back({U[i], (S[V[i]] ? 0 : 1)});
    }
    vector<int> sources;
    for (int i = 0; i < N; ++i) {
      if (two_source[i]) sources.push_back(i);
    }
    debug(sources);
    auto foo = SP(g, sources);
    for (int i = 0; i < N; ++i) {
      two_d[i] = int(foo[i]);
    }
  } else {
    two_d.assign(N, N + 1);
  }
  debug(two_d, single_d);
  vector<Poly> eq(N);
  for (auto v : X) {
    Poly single{single_d[v], 2};
    Poly two{two_d[v], 1};
    int isect = max(1, int(two[0] - single[0]));
    eq[1] += single;
    if (isect < N) {
      eq[isect] += two - single;
    }
  }
  for (int i = 2; i < N; ++i) {
    eq[i] += eq[i - 1];
  }
  debug(eq);
  vector<int> sp(N);
  {
    vector<vector<array<int, 2>>> g(N);
    for (int i = 0; i < 2 * M; ++i) {
      g[V[i]].push_back({U[i], 1 + (S[V[i]] && V[i] != Z ? N + 1 : 0)});
    }
    auto foo = SP(g, {Z});
    for (int i = 0; i < N; ++i) {
      if (foo[i] > N) {
        sp[i] = -1;
      } else {
        sp[i] = int(foo[i]);
      }
    }
  }
  if (all_zero) {
    for (int i = 0; i < N; ++i) {
      cout << sp[i] << '\n';
    }
    return 0;
  }  
  debug(sp);
  int B = 300;
  if (K <= B && !IWANNATEST) {
    vector<int64_t> ans(N, inf);
    for (int i = 0; i < N; ++i) {
      if (sp[i] != -1) ans[i] = sp[i];
    }
    for (int j = 1; j < N; ++j) {
      if (eq[j] != eq[j - 1]) {
        auto e = eq[j];
        vector<vector<array<int, 2>>> g(N);
        for (int i = 0; i < 2 * M; ++i) {
          g[V[i]].push_back({U[i], 1 + (S[V[i]] && V[i] != Z ? int(e[1]) : 0)});
        }
        auto dist = SP(g, {Z});
        debug(e, g, dist);
        for (int i = 0; i < N; ++i) {
          if (dist[i] != sp[i]) ans[i] = min(ans[i], e[0] + dist[i]);
        }
      }
    }
    for (int i = 0; i < N; ++i) {
      cout << ans[i] << '\n';
    }
  } else {
    B = N / B + 1;
    vector<int> closest(N);
    {
      vector<vector<array<int, 2>>> g(N);
      for (int i = 0; i < 2 * M; ++i) {
        g[V[i]].push_back({U[i], (S[V[i]] && V[i] != Z ? 1 : 0)});
      }
      auto foo = SP(g, {Z});
      for (int i = 0; i < N; ++i) {
        closest[i] = int(foo[i]);
      }
    }
    debug(closest);
    vector<vector<array<int, 2>>> g(N * B);
    auto Var = [&](int x, int y) {
      assert(y >= closest[x]);
      if (y >= closest[x] + B) return -1;
      return B * x + (y - closest[x]);
    };
    auto Add_edge = [&](int x, int y, int w) {
      if (x == -1 || y == -1) return;
      g[x].push_back({y, w}); //this satisties w = 1 so you can turn it to BFS if it TLE's (L situation) (called it)
    };
    for (int i = 0; i < 2 * M; ++i) {
      int stops = (S[V[i]] && V[i] != Z);
      int c = closest[V[i]];
      for (int j = c; j < c + B; ++j) {
        Add_edge(Var(V[i], j), Var(U[i], j + stops), 1);
      }
    }
    auto dist = BFS(g, {Var(Z, 0)}); 
    for (int i = 0; i < N; ++i) {
      int64_t ans = inf;
      if (sp[i] != -1) ans = sp[i];
      int c = closest[i];
      for (int j = max(c, 1); j < min(c + B, N); ++j) {
        int v = Var(i, j);
        if (dist[v] != -1) ans = min(ans, eval(eq[j], j) + dist[Var(i, j)]);
      }
      cout << ans << '\n';
    }
  }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 11 ms 3672 KB Output is correct
3 Correct 16 ms 5980 KB Output is correct
4 Correct 14 ms 5976 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4952 KB Output is correct
2 Correct 660 ms 384104 KB Output is correct
3 Correct 865 ms 6448 KB Output is correct
4 Correct 36 ms 6452 KB Output is correct
5 Correct 1730 ms 1041172 KB Output is correct
6 Correct 74 ms 7476 KB Output is correct
7 Correct 132 ms 6252 KB Output is correct
8 Correct 41 ms 7064 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4696 KB Output is correct
2 Correct 631 ms 383632 KB Output is correct
3 Correct 1696 ms 1042304 KB Output is correct
4 Correct 1655 ms 1028884 KB Output is correct
5 Correct 1600 ms 1029256 KB Output is correct
6 Correct 54 ms 7476 KB Output is correct
7 Correct 152 ms 7220 KB Output is correct
8 Correct 1612 ms 1027408 KB Output is correct
9 Correct 182 ms 94148 KB Output is correct
10 Correct 20 ms 4032 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 5 ms 604 KB Output is correct
3 Correct 7 ms 4696 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 4 ms 2016 KB Output is correct
8 Correct 7 ms 4628 KB Output is correct
9 Correct 2 ms 800 KB Output is correct
10 Correct 2 ms 772 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 12 ms 604 KB Output is correct
16 Correct 23 ms 604 KB Output is correct
17 Correct 59 ms 804 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 3 ms 804 KB Output is correct
20 Correct 4 ms 604 KB Output is correct
21 Correct 7 ms 4880 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 6964 KB Output is correct
2 Correct 53 ms 6548 KB Output is correct
3 Correct 38 ms 6456 KB Output is correct
4 Correct 51 ms 6800 KB Output is correct
5 Correct 57 ms 6712 KB Output is correct
6 Correct 36 ms 5504 KB Output is correct
7 Correct 21 ms 3584 KB Output is correct
8 Correct 22 ms 3876 KB Output is correct
9 Correct 22 ms 3876 KB Output is correct
10 Correct 37 ms 6344 KB Output is correct
11 Correct 40 ms 6240 KB Output is correct
12 Correct 34 ms 6452 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 6964 KB Output is correct
2 Correct 53 ms 6548 KB Output is correct
3 Correct 38 ms 6456 KB Output is correct
4 Correct 51 ms 6800 KB Output is correct
5 Correct 57 ms 6712 KB Output is correct
6 Correct 36 ms 5504 KB Output is correct
7 Correct 21 ms 3584 KB Output is correct
8 Correct 22 ms 3876 KB Output is correct
9 Correct 22 ms 3876 KB Output is correct
10 Correct 37 ms 6344 KB Output is correct
11 Correct 40 ms 6240 KB Output is correct
12 Correct 34 ms 6452 KB Output is correct
13 Correct 109 ms 6820 KB Output is correct
14 Correct 61 ms 6440 KB Output is correct
15 Correct 223 ms 7028 KB Output is correct
16 Correct 197 ms 6916 KB Output is correct
17 Correct 37 ms 6384 KB Output is correct
18 Correct 126 ms 6100 KB Output is correct
19 Correct 122 ms 5692 KB Output is correct
20 Correct 66 ms 6612 KB Output is correct
21 Correct 22 ms 3952 KB Output is correct
22 Correct 21 ms 4032 KB Output is correct
23 Correct 22 ms 3868 KB Output is correct
24 Correct 39 ms 6312 KB Output is correct
25 Correct 37 ms 6492 KB Output is correct
26 Correct 37 ms 6216 KB Output is correct
27 Correct 31 ms 3996 KB Output is correct
28 Correct 186 ms 3996 KB Output is correct
29 Correct 383 ms 4092 KB Output is correct
30 Correct 42 ms 6700 KB Output is correct
31 Correct 339 ms 6452 KB Output is correct
32 Correct 644 ms 6196 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 5 ms 604 KB Output is correct
3 Correct 7 ms 4696 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 4 ms 2016 KB Output is correct
8 Correct 7 ms 4628 KB Output is correct
9 Correct 2 ms 800 KB Output is correct
10 Correct 2 ms 772 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 12 ms 604 KB Output is correct
16 Correct 23 ms 604 KB Output is correct
17 Correct 59 ms 804 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 3 ms 804 KB Output is correct
20 Correct 4 ms 604 KB Output is correct
21 Correct 7 ms 4880 KB Output is correct
22 Correct 63 ms 4188 KB Output is correct
23 Correct 650 ms 383448 KB Output is correct
24 Correct 29 ms 4024 KB Output is correct
25 Correct 631 ms 4168 KB Output is correct
26 Correct 614 ms 378224 KB Output is correct
27 Correct 651 ms 378444 KB Output is correct
28 Correct 527 ms 372856 KB Output is correct
29 Correct 597 ms 374160 KB Output is correct
30 Correct 38 ms 4188 KB Output is correct
31 Correct 647 ms 378452 KB Output is correct
32 Correct 904 ms 3300 KB Output is correct
33 Correct 380 ms 189396 KB Output is correct
34 Correct 20 ms 4016 KB Output is correct
35 Correct 20 ms 3844 KB Output is correct
36 Correct 20 ms 4056 KB Output is correct
37 Correct 582 ms 353128 KB Output is correct
38 Correct 588 ms 350104 KB Output is correct
39 Correct 552 ms 4008 KB Output is correct
40 Correct 737 ms 3984 KB Output is correct
41 Correct 1121 ms 4000 KB Output is correct
42 Correct 577 ms 363180 KB Output is correct
43 Correct 501 ms 363160 KB Output is correct
44 Correct 519 ms 363156 KB Output is correct
45 Correct 519 ms 363180 KB Output is correct
46 Correct 527 ms 363160 KB Output is correct
47 Correct 529 ms 363156 KB Output is correct
48 Correct 537 ms 363072 KB Output is correct
49 Correct 534 ms 363112 KB Output is correct
50 Correct 564 ms 363236 KB Output is correct
51 Correct 23 ms 4016 KB Output is correct
52 Correct 38 ms 4012 KB Output is correct
53 Correct 55 ms 3856 KB Output is correct
54 Correct 533 ms 363252 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 11 ms 3672 KB Output is correct
3 Correct 16 ms 5980 KB Output is correct
4 Correct 14 ms 5976 KB Output is correct
5 Correct 8 ms 4952 KB Output is correct
6 Correct 660 ms 384104 KB Output is correct
7 Correct 865 ms 6448 KB Output is correct
8 Correct 36 ms 6452 KB Output is correct
9 Correct 1730 ms 1041172 KB Output is correct
10 Correct 74 ms 7476 KB Output is correct
11 Correct 132 ms 6252 KB Output is correct
12 Correct 41 ms 7064 KB Output is correct
13 Correct 7 ms 4696 KB Output is correct
14 Correct 631 ms 383632 KB Output is correct
15 Correct 1696 ms 1042304 KB Output is correct
16 Correct 1655 ms 1028884 KB Output is correct
17 Correct 1600 ms 1029256 KB Output is correct
18 Correct 54 ms 7476 KB Output is correct
19 Correct 152 ms 7220 KB Output is correct
20 Correct 1612 ms 1027408 KB Output is correct
21 Correct 182 ms 94148 KB Output is correct
22 Correct 20 ms 4032 KB Output is correct
23 Correct 2 ms 604 KB Output is correct
24 Correct 5 ms 604 KB Output is correct
25 Correct 7 ms 4696 KB Output is correct
26 Correct 5 ms 604 KB Output is correct
27 Correct 5 ms 604 KB Output is correct
28 Correct 4 ms 604 KB Output is correct
29 Correct 4 ms 2016 KB Output is correct
30 Correct 7 ms 4628 KB Output is correct
31 Correct 2 ms 800 KB Output is correct
32 Correct 2 ms 772 KB Output is correct
33 Correct 2 ms 604 KB Output is correct
34 Correct 2 ms 604 KB Output is correct
35 Correct 2 ms 604 KB Output is correct
36 Correct 2 ms 604 KB Output is correct
37 Correct 12 ms 604 KB Output is correct
38 Correct 23 ms 604 KB Output is correct
39 Correct 59 ms 804 KB Output is correct
40 Correct 2 ms 604 KB Output is correct
41 Correct 3 ms 804 KB Output is correct
42 Correct 4 ms 604 KB Output is correct
43 Correct 7 ms 4880 KB Output is correct
44 Correct 47 ms 6964 KB Output is correct
45 Correct 53 ms 6548 KB Output is correct
46 Correct 38 ms 6456 KB Output is correct
47 Correct 51 ms 6800 KB Output is correct
48 Correct 57 ms 6712 KB Output is correct
49 Correct 36 ms 5504 KB Output is correct
50 Correct 21 ms 3584 KB Output is correct
51 Correct 22 ms 3876 KB Output is correct
52 Correct 22 ms 3876 KB Output is correct
53 Correct 37 ms 6344 KB Output is correct
54 Correct 40 ms 6240 KB Output is correct
55 Correct 34 ms 6452 KB Output is correct
56 Correct 109 ms 6820 KB Output is correct
57 Correct 61 ms 6440 KB Output is correct
58 Correct 223 ms 7028 KB Output is correct
59 Correct 197 ms 6916 KB Output is correct
60 Correct 37 ms 6384 KB Output is correct
61 Correct 126 ms 6100 KB Output is correct
62 Correct 122 ms 5692 KB Output is correct
63 Correct 66 ms 6612 KB Output is correct
64 Correct 22 ms 3952 KB Output is correct
65 Correct 21 ms 4032 KB Output is correct
66 Correct 22 ms 3868 KB Output is correct
67 Correct 39 ms 6312 KB Output is correct
68 Correct 37 ms 6492 KB Output is correct
69 Correct 37 ms 6216 KB Output is correct
70 Correct 31 ms 3996 KB Output is correct
71 Correct 186 ms 3996 KB Output is correct
72 Correct 383 ms 4092 KB Output is correct
73 Correct 42 ms 6700 KB Output is correct
74 Correct 339 ms 6452 KB Output is correct
75 Correct 644 ms 6196 KB Output is correct
76 Correct 63 ms 4188 KB Output is correct
77 Correct 650 ms 383448 KB Output is correct
78 Correct 29 ms 4024 KB Output is correct
79 Correct 631 ms 4168 KB Output is correct
80 Correct 614 ms 378224 KB Output is correct
81 Correct 651 ms 378444 KB Output is correct
82 Correct 527 ms 372856 KB Output is correct
83 Correct 597 ms 374160 KB Output is correct
84 Correct 38 ms 4188 KB Output is correct
85 Correct 647 ms 378452 KB Output is correct
86 Correct 904 ms 3300 KB Output is correct
87 Correct 380 ms 189396 KB Output is correct
88 Correct 20 ms 4016 KB Output is correct
89 Correct 20 ms 3844 KB Output is correct
90 Correct 20 ms 4056 KB Output is correct
91 Correct 582 ms 353128 KB Output is correct
92 Correct 588 ms 350104 KB Output is correct
93 Correct 552 ms 4008 KB Output is correct
94 Correct 737 ms 3984 KB Output is correct
95 Correct 1121 ms 4000 KB Output is correct
96 Correct 577 ms 363180 KB Output is correct
97 Correct 501 ms 363160 KB Output is correct
98 Correct 519 ms 363156 KB Output is correct
99 Correct 519 ms 363180 KB Output is correct
100 Correct 527 ms 363160 KB Output is correct
101 Correct 529 ms 363156 KB Output is correct
102 Correct 537 ms 363072 KB Output is correct
103 Correct 534 ms 363112 KB Output is correct
104 Correct 564 ms 363236 KB Output is correct
105 Correct 23 ms 4016 KB Output is correct
106 Correct 38 ms 4012 KB Output is correct
107 Correct 55 ms 3856 KB Output is correct
108 Correct 533 ms 363252 KB Output is correct
109 Correct 1740 ms 1042448 KB Output is correct
110 Correct 1714 ms 1042936 KB Output is correct
111 Correct 679 ms 7580 KB Output is correct
112 Correct 732 ms 7456 KB Output is correct
113 Correct 1730 ms 1028880 KB Output is correct
114 Correct 284 ms 7456 KB Output is correct
115 Correct 412 ms 7444 KB Output is correct
116 Correct 89 ms 7504 KB Output is correct
117 Correct 1305 ms 711180 KB Output is correct
118 Correct 189 ms 94240 KB Output is correct
119 Correct 183 ms 93688 KB Output is correct
120 Correct 1158 ms 653972 KB Output is correct
121 Correct 1618 ms 1027084 KB Output is correct
122 Correct 35 ms 6980 KB Output is correct
123 Correct 1518 ms 975848 KB Output is correct
124 Correct 1564 ms 973320 KB Output is correct
125 Correct 1540 ms 976400 KB Output is correct
126 Correct 988 ms 7220 KB Output is correct
127 Correct 1322 ms 7212 KB Output is correct
128 Correct 1984 ms 7208 KB Output is correct
129 Correct 1457 ms 985876 KB Output is correct
130 Correct 1474 ms 985876 KB Output is correct
131 Correct 1504 ms 985872 KB Output is correct
132 Correct 1483 ms 985868 KB Output is correct
133 Correct 1494 ms 985876 KB Output is correct
134 Correct 1485 ms 985888 KB Output is correct
135 Correct 1493 ms 985872 KB Output is correct
136 Correct 1497 ms 985896 KB Output is correct
137 Correct 1514 ms 986000 KB Output is correct
138 Correct 1538 ms 986000 KB Output is correct
139 Correct 1563 ms 986208 KB Output is correct
140 Correct 43 ms 7088 KB Output is correct
141 Correct 66 ms 7084 KB Output is correct
142 Correct 1490 ms 985876 KB Output is correct
143 Correct 1306 ms 986476 KB Output is correct