Submission #1450002
Source Code Expand
/+ dub.sdl: name "F" dependency "dcomp" version=">=0.6.0" +/ import std.stdio, std.algorithm, std.range, std.conv; // import dcomp.foundation, dcomp.scanner; int main() { auto sc = new Scanner(stdin); int n; int[] a, b; sc.read(n, a, b); int[][] ga = new int[][](n); int[][] gb = new int[][](n); int ra, rb; foreach (i; 0..n) { if (a[i] != -1) { a[i]--; ga[a[i]] ~= i; } else { ra = i; } if (b[i] != -1) { b[i]--; gb[b[i]] ~= i; } else { rb = i; } } int[][] g = new int[][](n); bool[] zr = new bool[](n); int[][] tr; int dfs(int p) { int m = tr[p].length.to!int; if (m % 2) { zr[p] = true; } int[] v = new int[m]; foreach (i; 0..m) { v[i] = dfs(tr[p][i]); } foreach (i; 0..m/2) { int x = v[2*i], y = v[2*i+1]; g[x] ~= y; g[y] ~= x; } if (m % 2 == 0) { return p; } return v[$-1]; } int xx, yy; tr = ga; xx = dfs(ra); tr = gb; yy = dfs(rb); debug writeln(zr); debug writeln(g.map!(v => v.length).array); if (zr[xx] || zr[yy]) { writeln("IMPOSSIBLE"); return 0; } foreach (i; 0..n) { if (zr[i] && g[i].length) { writeln("IMPOSSIBLE"); return 0; } } int[] col = new int[](n); void mark(int p, int c) { col[p] = c; foreach (d; g[p]) { if (col[d]) continue; mark(d, -c); } } foreach (i; 0..n) { if (col[i]) continue; if (zr[i]) continue; mark(i, 1); } writeln("POSSIBLE"); writeln(col.map!(to!string).join(" ")); return 0; } /* IMPORT /home/yosupo/Program/dcomp/source/dcomp/foundation.d */ // module dcomp.foundation; static if (__VERSION__ <= 2070) { 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); } } } } version (X86) static if (__VERSION__ < 2071) { import core.bitop : bsf, bsr, popcnt; int bsf(ulong v) { foreach (i; 0..64) { if (v & (1UL << i)) return i; } return -1; } int bsr(ulong v) { foreach_reverse (i; 0..64) { if (v & (1UL << i)) return i; } return -1; } int popcnt(ulong v) { int c = 0; foreach (i; 0..64) { if (v & (1UL << i)) c++; } return c; } } /* IMPORT /home/yosupo/Program/dcomp/source/dcomp/scanner.d */ // module dcomp.scanner; 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 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; if (f.eof) return false; line = lineBuf[]; f.readln(line); } 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 { auto buf = line.split.map!(to!E).array; static if (isStaticArray!T) { assert(buf.length == T.length); } x = buf; line.length = 0; } } 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); } } }
Submission Info
Submission Time | |
---|---|
Task | F - Two Trees |
User | yosupo |
Language | D (LDC 0.17.0) |
Score | 1700 |
Code Size | 4987 Byte |
Status | AC |
Exec Time | 109 ms |
Memory | 27324 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1700 / 1700 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_47.txt, subtask_1_48.txt, subtask_1_49.txt, subtask_1_50.txt, subtask_1_51.txt, subtask_1_52.txt, subtask_1_53.txt, subtask_1_54.txt, subtask_1_55.txt, subtask_1_56.txt, subtask_1_57.txt, subtask_1_58.txt, subtask_1_59.txt, subtask_1_60.txt, subtask_1_61.txt, subtask_1_62.txt, subtask_1_63.txt, subtask_1_64.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 1 ms | 256 KB |
sample_02.txt | AC | 1 ms | 256 KB |
sample_03.txt | AC | 1 ms | 256 KB |
subtask_1_01.txt | AC | 1 ms | 256 KB |
subtask_1_02.txt | AC | 1 ms | 256 KB |
subtask_1_03.txt | AC | 57 ms | 11084 KB |
subtask_1_04.txt | AC | 78 ms | 14268 KB |
subtask_1_05.txt | AC | 84 ms | 16628 KB |
subtask_1_06.txt | AC | 25 ms | 4732 KB |
subtask_1_07.txt | AC | 67 ms | 14460 KB |
subtask_1_08.txt | AC | 29 ms | 6420 KB |
subtask_1_09.txt | AC | 49 ms | 9888 KB |
subtask_1_10.txt | AC | 65 ms | 13576 KB |
subtask_1_11.txt | AC | 19 ms | 4732 KB |
subtask_1_12.txt | AC | 86 ms | 18460 KB |
subtask_1_13.txt | AC | 63 ms | 12140 KB |
subtask_1_14.txt | AC | 13 ms | 4348 KB |
subtask_1_15.txt | AC | 28 ms | 7292 KB |
subtask_1_16.txt | AC | 47 ms | 11588 KB |
subtask_1_17.txt | AC | 36 ms | 6124 KB |
subtask_1_18.txt | AC | 87 ms | 18924 KB |
subtask_1_19.txt | AC | 88 ms | 17852 KB |
subtask_1_20.txt | AC | 105 ms | 22588 KB |
subtask_1_21.txt | AC | 93 ms | 25148 KB |
subtask_1_22.txt | AC | 81 ms | 25148 KB |
subtask_1_23.txt | AC | 107 ms | 20668 KB |
subtask_1_24.txt | AC | 92 ms | 19004 KB |
subtask_1_25.txt | AC | 56 ms | 13488 KB |
subtask_1_26.txt | AC | 73 ms | 14644 KB |
subtask_1_27.txt | AC | 99 ms | 19640 KB |
subtask_1_28.txt | AC | 84 ms | 16060 KB |
subtask_1_29.txt | AC | 103 ms | 20028 KB |
subtask_1_30.txt | AC | 91 ms | 21436 KB |
subtask_1_31.txt | AC | 88 ms | 27324 KB |
subtask_1_32.txt | AC | 103 ms | 21436 KB |
subtask_1_33.txt | AC | 92 ms | 19132 KB |
subtask_1_34.txt | AC | 56 ms | 14768 KB |
subtask_1_35.txt | AC | 74 ms | 15540 KB |
subtask_1_36.txt | AC | 97 ms | 21304 KB |
subtask_1_37.txt | AC | 103 ms | 20284 KB |
subtask_1_38.txt | AC | 103 ms | 22204 KB |
subtask_1_39.txt | AC | 104 ms | 23996 KB |
subtask_1_40.txt | AC | 105 ms | 21692 KB |
subtask_1_41.txt | AC | 103 ms | 20796 KB |
subtask_1_42.txt | AC | 66 ms | 15920 KB |
subtask_1_43.txt | AC | 109 ms | 20024 KB |
subtask_1_44.txt | AC | 103 ms | 20668 KB |
subtask_1_45.txt | AC | 103 ms | 21308 KB |
subtask_1_46.txt | AC | 104 ms | 20412 KB |
subtask_1_47.txt | AC | 102 ms | 21180 KB |
subtask_1_48.txt | AC | 109 ms | 22460 KB |
subtask_1_49.txt | AC | 68 ms | 17200 KB |
subtask_1_50.txt | AC | 96 ms | 19896 KB |
subtask_1_51.txt | AC | 103 ms | 21692 KB |
subtask_1_52.txt | AC | 104 ms | 21308 KB |
subtask_1_53.txt | AC | 102 ms | 21180 KB |
subtask_1_54.txt | AC | 105 ms | 20028 KB |
subtask_1_55.txt | AC | 105 ms | 20668 KB |
subtask_1_56.txt | AC | 68 ms | 17968 KB |
subtask_1_57.txt | AC | 96 ms | 21176 KB |
subtask_1_58.txt | AC | 101 ms | 22332 KB |
subtask_1_59.txt | AC | 103 ms | 22332 KB |
subtask_1_60.txt | AC | 102 ms | 22204 KB |
subtask_1_61.txt | AC | 105 ms | 21180 KB |
subtask_1_62.txt | AC | 103 ms | 23356 KB |
subtask_1_63.txt | AC | 70 ms | 20400 KB |
subtask_1_64.txt | AC | 99 ms | 20024 KB |