Submission #1814864
Source Code Expand
/+ dub.sdl: name "B" dependency "dcomp" version=">=0.7.4" +/ import std.stdio, std.algorithm, std.range, std.conv; // import dcomp.foundation, dcomp.scanner; // import dcomp.graph.bipatitematching; bool solve(bool[][] v) { int L = 10^^9; foreach (x; v) L = min(L, x.length.to!int); L += 3; int n = v.length.to!int; // writeln(v); auto bm = BipatiteMatching(n, n); foreach (i; 0..n) { foreach (j; 0..n) { if (i < v[j].length && v[j][i]) { bm.add(i, j); } } } if (bm.count == n) return true; foreach (i; n..L) { bm.delL(i % n); int[] nv; foreach (j; 0..n) { if (i < v[j].length && v[j][i]) { nv ~= j; // bm.add(i % n, j); } } bm.addL(i % n, nv); if (bm.count == n) return true; } return false; } int main() { Scanner sc = new Scanner(stdin); int n; sc.read(n); string[] sv = new string[n]; foreach (i; 0..n) { sc.read(sv[i]); } foreach (i; 0..26) { bool[][] v = sv.map!(x => x.map!(c => c-'a' == i).array).array; if (solve(v)) { writeln("YES"); return 0; } } writeln("NO"); return 0; } /* IMPORT /home/yosupo/Program/dcomp/source/dcomp/graph/bipatitematching.d */ // module dcomp.graph.bipatitematching; struct BipatiteMatching { int L, R, count; int[][] g; int[] lmt, rmt; int[] visited; int vc; this(int L, int R) { this.L = L; this.R = R; g = new int[][L]; visited = new int[L]; lmt = new int[L]; lmt[] = -1; rmt = new int[R]; rmt[] = -1; } bool dfs(int l) { if (l == -1) return true; if (visited[l] == vc) return false; visited[l] = vc; foreach (r; g[l]) { if (dfs(rmt[r])) { lmt[l] = r; rmt[r] = l; return true; } } return false; } void exec() { vc++; foreach (i; 0..L) { if (lmt[i] != -1) continue; if (g[i].length == 0) continue; if (dfs(i)) count++; } } void add(int l, int r) { g[l] ~= r; exec(); } void del(int l, int r) { import std.algorithm : remove; g[l] = g[l].remove!(a => a == r); if (rmt[r] == l) { count--; lmt[l] = rmt[r] = -1; exec(); } } void addL(int l, int[] v) { g[l] = v.dup; vc++; if (dfs(l)) count++; } void delL(int l) { g[l] = []; if (lmt[l] != -1) { int r = lmt[l]; count--; lmt[l] = rmt[r] = -1; exec(); } } } /* IMPORT /home/yosupo/Program/dcomp/source/dcomp/foundation.d */ // module dcomp.foundation; static if (__VERSION__ <= 2070) { /* Copied by https://github.com/dlang/phobos/blob/master/std/algorithm/iteration.d Copyright: Andrei Alexandrescu 2008-. License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0). */ template fold(fun...) if (fun.length >= 1) { auto fold(R, S...)(R r, S seed) { import std.algorithm : reduce; static if (S.length < 2) { return reduce!fun(seed, r); } else { import std.typecons : tuple; return reduce!fun(tuple(seed), r); } } } } import core.bitop : popcnt; static if (!__traits(compiles, popcnt(ulong.max))) { public import core.bitop : popcnt; int popcnt(ulong v) { return popcnt(cast(uint)(v)) + popcnt(cast(uint)(v>>32)); } } bool poppar(ulong v) { v^=v>>1; v^=v>>2; v&=0x1111111111111111UL; v*=0x1111111111111111UL; return ((v>>60) & 1) != 0; } /* IMPORT /home/yosupo/Program/dcomp/source/dcomp/scanner.d */ // module dcomp.scanner; // import dcomp.array; class Scanner { import std.stdio : File; import std.conv : to; import std.range : front, popFront, array, ElementType; import std.array : split; import std.traits : isSomeChar, isStaticArray, isArray; import std.algorithm : map; File f; this(File f) { this.f = f; } char[512] lineBuf; char[] line; private bool succW() { import std.range.primitives : empty, front, popFront; import std.ascii : isWhite; while (!line.empty && line.front.isWhite) { line.popFront; } return !line.empty; } private bool succ() { import std.range.primitives : empty, front, popFront; import std.ascii : isWhite; while (true) { while (!line.empty && line.front.isWhite) { line.popFront; } if (!line.empty) break; line = lineBuf[]; f.readln(line); if (!line.length) return false; } return true; } private bool readSingle(T)(ref T x) { import std.algorithm : findSplitBefore; import std.string : strip; import std.conv : parse; if (!succ()) return false; static if (isArray!T) { alias E = ElementType!T; static if (isSomeChar!E) { auto r = line.findSplitBefore(" "); x = r[0].strip.dup; line = r[1]; } else static if (isStaticArray!T) { foreach (i; 0..T.length) { bool f = succW(); assert(f); x[i] = line.parse!E; } } else { FastAppender!(E[]) buf; while (succW()) { buf ~= line.parse!E; } x = buf.data; } } else { x = line.parse!T; } return true; } int read(T, Args...)(ref T x, auto ref Args args) { if (!readSingle(x)) return 0; static if (args.length == 0) { return 1; } else { return 1 + read(args); } } } /* IMPORT /home/yosupo/Program/dcomp/source/dcomp/array.d */ // module dcomp.array; T[N] fixed(T, size_t N)(T[N] a) {return a;} struct FastAppender(A, size_t MIN = 4) { import std.algorithm : max; import std.conv; import std.range.primitives : ElementEncodingType; import core.stdc.string : memcpy; private alias T = ElementEncodingType!A; private T* _data; private uint len, cap; @property size_t length() const {return len;} bool empty() const { return len == 0; } void reserve(size_t nlen) { import core.memory : GC; if (nlen <= cap) return; void* nx = GC.malloc(nlen * T.sizeof); cap = nlen.to!uint; if (len) memcpy(nx, _data, len * T.sizeof); _data = cast(T*)(nx); } void free() { import core.memory : GC; GC.free(_data); } void opOpAssign(string op : "~")(T item) { if (len == cap) { reserve(max(MIN, cap*2)); } _data[len++] = item; } void insertBack(T item) { this ~= item; } void removeBack() { len--; } void clear() { len = 0; } ref inout(T) back() inout { assert(len); return _data[len-1]; } ref inout(T) opIndex(size_t i) inout { return _data[i]; } T[] data() { return (_data) ? _data[0..len] : null; } } /* This source code generated by dcomp and include dcomp's source code. dcomp's Copyright: Copyright (c) 2016- Kohei Morita. (https://github.com/yosupo06/dcomp) dcomp's License: MIT License(https://github.com/yosupo06/dcomp/blob/master/LICENSE.txt) */
Submission Info
Submission Time | |
---|---|
Task | B - コメント |
User | yosupo |
Language | D (LDC 0.17.0) |
Score | 0 |
Code Size | 8222 Byte |
Status | WA |
Exec Time | 97 ms |
Memory | 3964 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 30 | 0 / 60 | ||||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt |
Subtask1 | sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt |
Subtask2 | sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 1 ms | 256 KB |
sample_02.txt | AC | 1 ms | 256 KB |
subtask1_01.txt | AC | 1 ms | 256 KB |
subtask1_02.txt | AC | 3 ms | 508 KB |
subtask1_03.txt | AC | 3 ms | 508 KB |
subtask1_04.txt | AC | 3 ms | 508 KB |
subtask1_05.txt | AC | 2 ms | 508 KB |
subtask1_06.txt | AC | 3 ms | 508 KB |
subtask1_07.txt | AC | 1 ms | 256 KB |
subtask1_08.txt | AC | 3 ms | 2684 KB |
subtask1_09.txt | AC | 1 ms | 256 KB |
subtask1_10.txt | AC | 3 ms | 508 KB |
subtask1_11.txt | AC | 3 ms | 508 KB |
subtask1_12.txt | WA | 3 ms | 508 KB |
subtask1_13.txt | AC | 2 ms | 380 KB |
subtask1_14.txt | AC | 3 ms | 508 KB |
subtask1_15.txt | AC | 2 ms | 380 KB |
subtask1_16.txt | AC | 3 ms | 508 KB |
subtask2_01.txt | AC | 5 ms | 764 KB |
subtask2_02.txt | AC | 58 ms | 1276 KB |
subtask2_03.txt | AC | 15 ms | 1404 KB |
subtask2_04.txt | AC | 41 ms | 1276 KB |
subtask2_05.txt | AC | 4 ms | 764 KB |
subtask2_06.txt | AC | 30 ms | 3964 KB |
subtask2_07.txt | AC | 2 ms | 764 KB |
subtask2_08.txt | AC | 4 ms | 764 KB |
subtask2_09.txt | AC | 56 ms | 1276 KB |
subtask2_10.txt | WA | 24 ms | 1276 KB |
subtask2_11.txt | AC | 52 ms | 1276 KB |
subtask2_12.txt | AC | 17 ms | 1276 KB |
subtask2_13.txt | AC | 6 ms | 1148 KB |
subtask2_14.txt | AC | 58 ms | 1276 KB |
subtask2_15.txt | AC | 10 ms | 1276 KB |
subtask2_16.txt | AC | 58 ms | 1276 KB |
subtask2_17.txt | AC | 63 ms | 2172 KB |
subtask2_18.txt | AC | 72 ms | 1276 KB |
subtask2_19.txt | AC | 60 ms | 3964 KB |
subtask2_20.txt | AC | 56 ms | 1276 KB |
subtask2_21.txt | AC | 74 ms | 1276 KB |
subtask2_22.txt | WA | 73 ms | 1276 KB |
subtask2_23.txt | WA | 55 ms | 1276 KB |
subtask2_24.txt | AC | 97 ms | 1276 KB |
subtask2_25.txt | WA | 73 ms | 1276 KB |
subtask2_26.txt | AC | 13 ms | 1276 KB |
subtask2_27.txt | AC | 75 ms | 1276 KB |
subtask2_28.txt | AC | 75 ms | 1276 KB |