oj.uz

Submission #1042288

# Submission time Handle Problem Language Result Execution time Memory
1042288 2024-08-02T19:20:17 Z erray Board Game (JOI24_boardgame) C++17
77 / 100
 4000 ms 1021492 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;
}
 

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);
  constexpr 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 {
    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)
    };
    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 = SP(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 860 KB Output is correct
2 Correct 12 ms 4376 KB Output is correct
3 Correct 19 ms 7004 KB Output is correct
4 Correct 16 ms 6492 KB Output is correct

Subtask #2
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 61632 KB Output is correct
2 Correct 2468 ms 613280 KB Output is correct
3 Correct 863 ms 7068 KB Output is correct
4 Correct 35 ms 7220 KB Output is correct
5 Execution timed out 4069 ms 1019952 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 60680 KB Output is correct
2 Correct 2444 ms 612380 KB Output is correct
3 Execution timed out 4066 ms 1021492 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 185 ms 60760 KB Output is correct
4 Correct 7 ms 856 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 122 ms 39828 KB Output is correct
8 Correct 184 ms 61448 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 2 ms 720 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Correct 2 ms 600 KB Output is correct
13 Correct 2 ms 760 KB Output is correct
14 Correct 2 ms 600 KB Output is correct
15 Correct 14 ms 856 KB Output is correct
16 Correct 23 ms 828 KB Output is correct
17 Correct 57 ms 848 KB Output is correct
18 Correct 2 ms 600 KB Output is correct
19 Correct 3 ms 632 KB Output is correct
20 Correct 5 ms 600 KB Output is correct
21 Correct 162 ms 57028 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 7472 KB Output is correct
2 Correct 50 ms 7172 KB Output is correct
3 Correct 38 ms 7224 KB Output is correct
4 Correct 52 ms 7324 KB Output is correct
5 Correct 64 ms 7472 KB Output is correct
6 Correct 40 ms 6248 KB Output is correct
7 Correct 27 ms 4420 KB Output is correct
8 Correct 23 ms 4332 KB Output is correct
9 Correct 22 ms 4248 KB Output is correct
10 Correct 46 ms 6996 KB Output is correct
11 Correct 39 ms 6764 KB Output is correct
12 Correct 37 ms 7216 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 7472 KB Output is correct
2 Correct 50 ms 7172 KB Output is correct
3 Correct 38 ms 7224 KB Output is correct
4 Correct 52 ms 7324 KB Output is correct
5 Correct 64 ms 7472 KB Output is correct
6 Correct 40 ms 6248 KB Output is correct
7 Correct 27 ms 4420 KB Output is correct
8 Correct 23 ms 4332 KB Output is correct
9 Correct 22 ms 4248 KB Output is correct
10 Correct 46 ms 6996 KB Output is correct
11 Correct 39 ms 6764 KB Output is correct
12 Correct 37 ms 7216 KB Output is correct
13 Correct 114 ms 7544 KB Output is correct
14 Correct 66 ms 7212 KB Output is correct
15 Correct 222 ms 7644 KB Output is correct
16 Correct 216 ms 7704 KB Output is correct
17 Correct 42 ms 6952 KB Output is correct
18 Correct 129 ms 6576 KB Output is correct
19 Correct 132 ms 6352 KB Output is correct
20 Correct 67 ms 7128 KB Output is correct
21 Correct 22 ms 4208 KB Output is correct
22 Correct 27 ms 4276 KB Output is correct
23 Correct 24 ms 4360 KB Output is correct
24 Correct 38 ms 6768 KB Output is correct
25 Correct 57 ms 6996 KB Output is correct
26 Correct 47 ms 6980 KB Output is correct
27 Correct 30 ms 4264 KB Output is correct
28 Correct 186 ms 4268 KB Output is correct
29 Correct 381 ms 4512 KB Output is correct
30 Correct 40 ms 7088 KB Output is correct
31 Correct 337 ms 7212 KB Output is correct
32 Correct 645 ms 6964 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 4 ms 860 KB Output is correct
3 Correct 185 ms 60760 KB Output is correct
4 Correct 7 ms 856 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 122 ms 39828 KB Output is correct
8 Correct 184 ms 61448 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 2 ms 720 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Correct 2 ms 600 KB Output is correct
13 Correct 2 ms 760 KB Output is correct
14 Correct 2 ms 600 KB Output is correct
15 Correct 14 ms 856 KB Output is correct
16 Correct 23 ms 828 KB Output is correct
17 Correct 57 ms 848 KB Output is correct
18 Correct 2 ms 600 KB Output is correct
19 Correct 3 ms 632 KB Output is correct
20 Correct 5 ms 600 KB Output is correct
21 Correct 162 ms 57028 KB Output is correct
22 Correct 60 ms 4452 KB Output is correct
23 Correct 2573 ms 613128 KB Output is correct
24 Correct 29 ms 4440 KB Output is correct
25 Correct 630 ms 4516 KB Output is correct
26 Correct 1940 ms 604284 KB Output is correct
27 Correct 2389 ms 611176 KB Output is correct
28 Correct 2072 ms 602136 KB Output is correct
29 Correct 2139 ms 603048 KB Output is correct
30 Correct 39 ms 4460 KB Output is correct
31 Correct 2397 ms 611372 KB Output is correct
32 Correct 894 ms 3688 KB Output is correct
33 Correct 1880 ms 461976 KB Output is correct
34 Correct 20 ms 4272 KB Output is correct
35 Correct 21 ms 4276 KB Output is correct
36 Correct 20 ms 4380 KB Output is correct
37 Correct 1928 ms 561688 KB Output is correct
38 Correct 1824 ms 556728 KB Output is correct
39 Correct 581 ms 4520 KB Output is correct
40 Correct 752 ms 4348 KB Output is correct
41 Correct 1124 ms 4264 KB Output is correct
42 Correct 1855 ms 565880 KB Output is correct
43 Correct 1893 ms 565928 KB Output is correct
44 Correct 1862 ms 565900 KB Output is correct
45 Correct 1892 ms 565920 KB Output is correct
46 Correct 2041 ms 565928 KB Output is correct
47 Correct 1894 ms 565920 KB Output is correct
48 Correct 1949 ms 565888 KB Output is correct
49 Correct 1979 ms 565976 KB Output is correct
50 Correct 2045 ms 566128 KB Output is correct
51 Correct 28 ms 4272 KB Output is correct
52 Correct 39 ms 4264 KB Output is correct
53 Correct 56 ms 4196 KB Output is correct
54 Correct 1445 ms 566184 KB Output is correct

Subtask #8
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 12 ms 4376 KB Output is correct
3 Correct 19 ms 7004 KB Output is correct
4 Correct 16 ms 6492 KB Output is correct
5 Correct 187 ms 61632 KB Output is correct
6 Correct 2468 ms 613280 KB Output is correct
7 Correct 863 ms 7068 KB Output is correct
8 Correct 35 ms 7220 KB Output is correct
9 Execution timed out 4069 ms 1019952 KB Time limit exceeded
10 Halted 0 ms 0 KB -