Submission #19001551


Source Code Expand

Copy
import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }


struct ModInt(int M_) {
  import std.conv : to;
  alias M = M_;
  int x;
  this(ModInt a) { x = a.x; }
  this(long a) { x = cast(int)(a % M); if (x < 0) x += M; }
  ref ModInt opAssign(long a) { return (this = ModInt(a)); }
  ref ModInt opOpAssign(string op)(ModInt a) {
    static if (op == "+") { x += a.x; if (x >= M) x -= M; }
    else static if (op == "-") { x -= a.x; if (x < 0) x += M; }
    else static if (op == "*") { x = cast(int)((cast(long)(x) * a.x) % M); }
    else static if (op == "/") { this *= a.inv(); }
    else static assert(false);
    return this;
  }
  ref ModInt opOpAssign(string op)(long a) {
    static if (op == "^^") {
      if (a < 0) return (this = inv()^^(-a));
      ModInt t2 = this, te = ModInt(1);
      for (long e = a; e > 0; e >>= 1) {
        if (e & 1) te *= t2;
        t2 *= t2;
      }
      x = cast(int)(te.x);
      return this;
    } else return mixin("this " ~ op ~ "= ModInt(a)");
  }
  ModInt inv() const {
    int a = x, b = M, y = 1, z = 0, t;
    for (; ; ) {
      t = a / b; a -= t * b;
      if (a == 0) {
        assert(b == 1 || b == -1);
        return ModInt(b * z);
      }
      y -= t * z;
      t = b / a; b -= t * a;
      if (b == 0) {
        assert(a == 1 || a == -1);
        return ModInt(a * y);
      }
      z -= t * y;
    }
  }
  ModInt opUnary(string op: "-")() const { return ModInt(-x); }
  ModInt opBinary(string op, T)(T a) const {
    return mixin("ModInt(this) " ~ op ~ "= a");
  }
  ModInt opBinaryRight(string op)(long a) const {
    return mixin("ModInt(a) " ~ op ~ "= this");
  }
  bool opCast(T: bool)() const { return (x != 0); }
  string toString() const { return x.to!string; }
}

enum MO = 998244353;
alias Mint = ModInt!MO;

enum LIM = 610;
int[][] bn;


int N;
int[] A, B;
int[] C;

int[][] G;
int[][][] dp;

int[] merge(int[] fs, int[] gs) {
  const m = cast(int)(fs.length) - 1;
  const n = cast(int)(gs.length) - 1;
  auto fsSum = new int[m + 1];
  auto gsSum = new int[n + 1];
  foreach_reverse (i; 0 .. m) {
    fsSum[i] = fs[i] + fsSum[i + 1];
  }
  foreach_reverse (j; 0 .. n) {
    gsSum[j] = gs[j] + gsSum[j + 1];
  }
  auto ret = new int[m + n + 1];
  ret[m + n] = fs[m] * gs[n];
  foreach (i; 0 .. m) {
    foreach (j; 0 .. n + 1) {
      ret[i + j] += bn[i + j][i] * fs[i] * gsSum[j];
    }
  }
  foreach (i; 0 .. m + 1) {
    foreach (j; 0 .. n) {
      ret[i + j] += bn[i + j][j] * fsSum[i] * gs[j];
    }
  }
  debug {
    writeln("merge ", fs, " ", gs, " = ", ret);
  }
  return ret;
}

int[] append(int[] fs, int c) {
  const m = cast(int)(fs.length) - 1;
  auto ret = new int[m + 1 + 1];
  foreach (i; 0 .. m) {
    ret[i] += fs[i];
  }
  ret[m + c] += fs[m];
  return ret;
}

int[] calc(int u, int p) {
  if (!dp[u][p]) {
    int[] ret = [1];
    foreach (i; G[u]) {
      const v = A[i] ^ B[i] ^ u;
      if (v != p) {
        auto res = calc(v, u);
        ret = merge(ret, res);
      }
    }
    ret = append(ret, C[u]);
    debug {
      writeln(u, " ", p, ": ", ret);
    }
    dp[u][p] = ret;
  }
  return dp[u][p];
}

void main() {
  bn = new int[][](LIM, LIM);
  foreach (n; 0 .. LIM) {
    bn[n][0] = bn[n][n] = 1;
    foreach (k; 1 .. n) {
      bn[n][k] = bn[n - 1][k - 1] + bn[n - 1][k];
    }
  }
  
  try {
    for (; ; ) {
      N = readInt();
      A = new int[N - 1];
      B = new int[N - 1];
      foreach (i; 0 .. N - 1) {
        A[i] = readInt() - 1;
        B[i] = readInt() - 1;
      }
      C = new int[N];
      foreach (u; 0 .. N) {
        C[u] = readInt();
      }
      
      G = new int[][N];
      foreach (i; 0 .. N - 1) {
        G[A[i]] ~= i;
        G[B[i]] ~= i;
      }
      dp = new int[][][](N + 1, N + 1);
      
      int ans;
      foreach (i0; 0 .. N - 1) {
        int[] fs = [1];
        foreach (u; [A[i0], B[i0]]) {
          foreach (i; G[u]) {
            const v = A[i] ^ B[i] ^ u;
            fs = merge(fs, calc(v, u));
          }
        }
        fs = append(fs, (C[A[i0]] & C[B[i0]]) ^ 1);
        foreach (k; 0 .. N) {
          if ((N - max(k, 1)) % 2 != 0) {
            ans += fs[k];
          }
        }
        if (N % 2 != 0) {
          ans += fs[N];
        }
      }
      writeln(ans & 1);
    }
  } catch (EOFException e) {
  }
}

Submission Info

Submission Time
Task F - NAND Tree
User hos_lyric
Language D (LDC 1.20.1)
Score 0
Code Size 5591 Byte
Status WA
Exec Time 235 ms
Memory 17956 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 2000
Status
AC × 2
WA × 1
AC × 52
WA × 51
Set Name Test Cases
Sample example0.txt, example1.txt, example2.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, 050.txt, 051.txt, 052.txt, 053.txt, 054.txt, 055.txt, 056.txt, 057.txt, 058.txt, 059.txt, 060.txt, 061.txt, 062.txt, 063.txt, 064.txt, 065.txt, 066.txt, 067.txt, 068.txt, 069.txt, 070.txt, 071.txt, 072.txt, 073.txt, 074.txt, 075.txt, 076.txt, 077.txt, 078.txt, 079.txt, 080.txt, 081.txt, 082.txt, 083.txt, 084.txt, 085.txt, 086.txt, 087.txt, 088.txt, 089.txt, 090.txt, 091.txt, 092.txt, 093.txt, 094.txt, 095.txt, 096.txt, 097.txt, 098.txt, 099.txt, example0.txt, example1.txt, example2.txt
Case Name Status Exec Time Memory
000.txt WA 5 ms 5984 KB
001.txt AC 231 ms 17956 KB
002.txt AC 233 ms 17864 KB
003.txt AC 232 ms 17344 KB
004.txt AC 235 ms 17732 KB
005.txt AC 232 ms 17084 KB
006.txt AC 38 ms 8360 KB
007.txt AC 95 ms 11264 KB
008.txt AC 144 ms 13652 KB
009.txt AC 34 ms 7264 KB
010.txt AC 127 ms 11740 KB
011.txt AC 10 ms 5888 KB
012.txt AC 6 ms 5772 KB
013.txt WA 6 ms 5832 KB
014.txt WA 6 ms 5896 KB
015.txt WA 7 ms 5772 KB
016.txt AC 14 ms 6244 KB
017.txt WA 29 ms 6788 KB
018.txt AC 35 ms 7340 KB
019.txt WA 56 ms 8688 KB
020.txt AC 148 ms 11936 KB
021.txt AC 150 ms 11072 KB
022.txt WA 203 ms 13156 KB
023.txt AC 234 ms 14168 KB
024.txt WA 7 ms 5716 KB
025.txt WA 26 ms 7024 KB
026.txt WA 7 ms 5984 KB
027.txt WA 16 ms 6352 KB
028.txt WA 56 ms 9400 KB
029.txt AC 31 ms 7572 KB
030.txt WA 139 ms 11264 KB
031.txt AC 10 ms 5964 KB
032.txt WA 11 ms 5832 KB
033.txt AC 115 ms 11096 KB
034.txt WA 141 ms 12572 KB
035.txt WA 138 ms 12636 KB
036.txt AC 141 ms 12420 KB
037.txt WA 136 ms 12572 KB
038.txt WA 139 ms 12540 KB
039.txt AC 138 ms 12844 KB
040.txt WA 136 ms 12624 KB
041.txt AC 226 ms 15884 KB
042.txt WA 224 ms 16316 KB
043.txt WA 229 ms 15628 KB
044.txt WA 145 ms 11792 KB
045.txt WA 142 ms 11792 KB
046.txt AC 145 ms 11784 KB
047.txt AC 146 ms 11796 KB
048.txt AC 144 ms 11692 KB
049.txt WA 145 ms 11768 KB
050.txt WA 144 ms 11536 KB
051.txt AC 144 ms 11912 KB
052.txt WA 147 ms 12004 KB
053.txt AC 142 ms 11772 KB
054.txt AC 6 ms 5716 KB
055.txt AC 6 ms 5840 KB
056.txt AC 6 ms 5808 KB
057.txt AC 9 ms 5836 KB
058.txt WA 8 ms 5836 KB
059.txt WA 8 ms 6068 KB
060.txt AC 33 ms 7808 KB
061.txt WA 144 ms 11156 KB
062.txt AC 207 ms 13620 KB
063.txt AC 202 ms 16004 KB
064.txt WA 71 ms 9396 KB
065.txt WA 64 ms 9656 KB
066.txt AC 165 ms 11780 KB
067.txt AC 156 ms 14940 KB
068.txt WA 207 ms 16564 KB
069.txt AC 65 ms 9940 KB
070.txt WA 46 ms 9024 KB
071.txt AC 35 ms 8612 KB
072.txt WA 170 ms 15556 KB
073.txt WA 158 ms 15316 KB
074.txt WA 154 ms 14040 KB
075.txt WA 98 ms 11572 KB
076.txt WA 100 ms 11364 KB
077.txt AC 101 ms 11240 KB
078.txt WA 77 ms 10304 KB
079.txt WA 43 ms 8512 KB
080.txt WA 184 ms 16020 KB
081.txt WA 74 ms 10172 KB
082.txt WA 173 ms 15128 KB
083.txt WA 203 ms 16744 KB
084.txt AC 139 ms 13200 KB
085.txt WA 45 ms 9048 KB
086.txt AC 68 ms 9912 KB
087.txt AC 156 ms 14632 KB
088.txt AC 38 ms 8372 KB
089.txt AC 161 ms 14772 KB
090.txt WA 35 ms 8268 KB
091.txt WA 203 ms 15220 KB
092.txt AC 206 ms 13308 KB
093.txt WA 203 ms 15052 KB
094.txt WA 209 ms 13252 KB
095.txt AC 139 ms 12244 KB
096.txt AC 68 ms 9388 KB
097.txt WA 69 ms 9120 KB
098.txt AC 160 ms 11672 KB
099.txt AC 157 ms 13620 KB
example0.txt AC 6 ms 5796 KB
example1.txt WA 6 ms 5844 KB
example2.txt AC 5 ms 5992 KB