Submission #1042290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042290		erray	Board Game (JOI24_boardgame)	C++17	100 / 100	1984 ms	1042936 KiB

Main

#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 / 3
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 19 / 19
• Subtask 5: 23 / 23
• Subtask 6: 9 / 9
• Subtask 7: 23 / 23
• Subtask 8: 9 / 9