Submission #1090972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090972		vjudge1	Topovi (COCI15_topovi)	C++14	0 / 120	380 ms	36684 KiB

topovi

// [COCI2015-2016#1] TOPOVI
#include <bits/stdc++.h>
using namespace std;
#define CAR const auto&
using LL = long long;
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int N, K, P;
  cin >> N >> K >> P;
  // if (N > 1000) {  // TODO: 优化
  //   return 0;
  // }
  unordered_map<int, int> R, C, RK, CK;
  using IP = array<int, 2>;
  map<IP, int> A;
  // R[r]/C[c]: 第r行/第c列的xor sum
  for (int i = 0, x, y, w; i < K and cin >> x >> y >> w; i++) {
    IP p{x, y};
    assert(!A.count(p));
    A[p] = w, R[x] ^= w, C[y] ^= w;
  }
  LL ans = 0;
  for (CAR p : R) ++RK[p.second];  // RK[k]: 有第几行 xor sum = k
  for (CAR p : C) ++CK[p.second];  // CK[k]: 有第几行 xor sum = k
  for (CAR p : CK) {
    int k = p.first, c = p.second;          // 有c列xor sum = k
    if (RK.count(k)) ans += LL(c) * RK[k];  // 有r行为k，对答案的贡献为r*c
  }
  auto cg_rk = [&](int r, int w) {  // RK[r] ^= w
    int x = R[r], y = x ^ w;        // 行r的 xor sum 从x 变化为 w
    ans -= CK.count(x) ? CK[x] : 0;
    ans += CK.count(y) ? CK[y] : 0;
    --RK[x], ++RK[y], R[r] = y;
  };
  auto cg_ck = [&](int c, int w) {  //
    int x = C[c], y = x ^ w;        // 列c的 xor sum 从x 变化为 w
    ans -= RK.count(x) ? RK[x] : 0;
    ans += RK.count(y) ? RK[y] : 0;
    --CK[x], ++CK[y], R[c] = y;
  };
  for (int i = 0, r1, c1, r2, c2; i < P and cin >> r1 >> c1 >> r2 >> c2; i++) {
    IP p1 = {r1, c1}, p2 = {r2, c2};
    assert(!A.count(p2));
    assert(A.count(p1));
    int w = A[p1];
    A.erase(p1), A[p2] = w;
    cg_rk(r1, w), cg_ck(c1, w), cg_rk(r2, w), cg_ck(c2, w);
    printf("%lld\n", ans);
  }
  return 0;
}
// ❓❓ 0

• Subtask 1: 0 / 120