Submission #1060013
Source Code Expand
/+ dub.sdl:
name "A"
dependency "dcomp" version=">=0.4.0"
+/
import std.stdio, std.algorithm, std.conv, std.range;
import std.typecons, std.math;
// import dcomp.scanner, dcomp.graph.namori;
alias E = Tuple!(int, "to");
long calc(E[][] g, int[] co) {
int n = g.length.to!int;
if (co.sum) return 10L^^18;
long[] sm = new long[n];
void dfs(int p, int b) {
sm[p] = co[p];
foreach (e; g[p]) {
int d = e.to;
if (d == b) continue;
dfs(d, p);
sm[p] += sm[d];
}
}
dfs(0, -1);
return sm.map!"abs(a)".sum;
}
long solve(E[][] g) {
int n = g.length.to!int;
int[] col = new int[n];
void dfs(int p, int b, int c) {
col[p] = c;
foreach (e; g[p]) {
int d = e.to;
if (d == b) continue;
dfs(d, p, -c);
}
}
dfs(0, -1, 1);
return calc(g, col);
}
int main() {
auto sc = new Scanner(stdin);
int n, m;
sc.read(n, m);
E[][] g = new E[][n];
foreach (i; 0..m) {
int a, b;
sc.read(a, b); a--; b--;
g[a] ~= E(b);
g[b] ~= E(a);
}
if (n % 2) {
writeln(-1);
return 0;
}
if (m == n-1) {
//not namori
auto ans = solve(g);
if (ans == 10L^^18) ans = -1;
writeln(ans);
return 0;
}
auto nmr = namori(g);
auto cy = nmr.cycles[0];
int a = cy[0], b = cy[1];
g[a] = g[a].remove!(e => e.to == b);
g[b] = g[b].remove!(e => e.to == a);
int[] col = new int[n];
void dfs(int p, int b, int c) {
col[p] = c;
foreach (E e; g[p]) {
int d = e.to;
if (d == b) continue;
dfs(d, p, -c);
}
}
dfs(a, -1, 1);
if (col.sum < 0) {
col[] *= -1;
}
if (cy.length % 2 == 0) {
if (col.sum) {
writeln(-1);
return 0;
}
long check(int md) {
auto buf = col.dup;
buf[a] += md;
buf[b] -= md;
// writeln(md, " ", buf, calc(g, buf));
return calc(g, buf)+abs(md);
}
int l = -2*n, r = 2*n;
// assert(check(l-1) >= check(l));
// assert(check(r) <= check(r+1));
while (r-l > 5) {
int mdl = (l+l+r)/3;
int mdr = (l+r+r)/3;
if (check(mdl) > check(mdr)) {
l = mdl;
} else {
r = mdr;
}
}
writeln(iota(l, r+1).map!(md => check(md)).reduce!"min(a, b)");
// assert(false);
} else {
int ad = col.sum/2;
col[a] -= ad;
col[b] -= ad;
writeln(ad + calc(g, col));
}
return 0;
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/graph/namori.d */
// module dcomp.graph.namori;
// import dcomp.graph.dfsinfo;
struct Namori {
bool[] isCycle;
int[][] cycles;
int[] root;
this(int n) {
isCycle = new bool[n];
root = new int[n];
}
}
Namori namori(T)(T g) {
import std.algorithm : find, each;
import std.range;
import std.conv : to;
int n = g.length.to!int;
auto info = dfsInfo(g);
auto nmr = Namori(n);
with (nmr) {
//find self loop
foreach (i; 0..n) {
if (g[i].find!(e => e.to == i).empty) continue;
isCycle[i] = true;
cycles ~= [i];
}
foreach (p; info.vlis) {
if (info.low[p] == info.ord[p]) continue;
if (g[p].length == info.tr[p].length+1) continue;
int[] v;
int nw = p;
while (info.ord[nw] != info.low[p]) {
v ~= nw;
nw = info.par[nw];
}
v ~= nw;
v.each!(i => isCycle[i] = true);
cycles ~= v;
}
bool[] used = new bool[n];
void dfs(int p, int b, int r) {
if (used[p]) return;
used[p] = true;
root[p] = r;
foreach (e; g[p]) {
int d = e.to;
if (d == b) continue;
if (isCycle[d]) continue;
dfs(d, p, r);
}
}
foreach (i; 0..n) {
if (!isCycle[i]) continue;
dfs(i, -1, i);
}
}
return nmr;
}
Namori directedNamori(int[] g) {
import std.algorithm : find, each;
import std.range;
import std.conv : to;
int n = g.length.to!int;
auto nmr = Namori(n);
with (nmr) {
int[] used = new int[n]; used[] = -1;
foreach (i; 0..n) {
if (used[i] != -1) continue;
int j = i;
while (used[j] == -1) {
used[j] = i;
j = g[j];
}
if (used[j] != i) continue;
int k = j;
int[] cy = [];
while (true) {
cy ~= k;
isCycle[k] = true;
if (g[k] == j) break;
k = g[k];
}
cycles ~= cy;
}
int[] dp = new int[n]; dp[] = -1;
int dfs(int p) {
if (isCycle[p]) return p;
if (dp[p] != -1) return dp[p];
return dp[p] = dfs(g[p]);
}
foreach (i; 0..n) {
root[i] = dfs(i);
}
}
return nmr;
}
/* 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;
}
string[] buf;
private bool succ() {
while (!buf.length) {
if (f.eof) return false;
buf = f.readln.split;
}
return true;
}
private bool readSingle(T)(ref T x) {
if (!succ()) return false;
static if (isArray!T) {
alias E = ElementType!T;
static if (isSomeChar!E) {
//string or char[10] etc
x = buf.front;
buf.popFront;
} else {
static if (isStaticArray!T) {
//static
assert(buf.length == T.length);
}
x = buf.map!(to!E).array;
buf.length = 0;
}
} else {
x = buf.front.to!T;
buf.popFront;
}
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);
}
}
}
unittest {
import std.path : buildPath;
import std.file : tempDir;
import std.algorithm : equal;
import std.stdio : File;
string fileName = buildPath(tempDir, "kyuridenanmaida.txt");
auto fout = File(fileName, "w");
fout.writeln("1 2 3");
fout.writeln("ab cde");
fout.writeln("1.0 1.0 2.0");
fout.close;
Scanner sc = new Scanner(File(fileName, "r"));
int a;
int[2] b;
char[2] c;
string d;
double e;
double[] f;
sc.read(a, b, c, d, e, f);
assert(a == 1);
assert(equal(b[], [2, 3]));
assert(equal(c[], "ab"));
assert(equal(d, "cde"));
assert(e == 1.0);
assert(equal(f, [1.0, 2.0]));
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/graph/dfsinfo.d */
// module dcomp.graph.dfsinfo;
struct DFSInfo {
int[] low, ord, par, vlis; //low, ord, parent, visitList
int[][] tr; //dfs tree(directed)
this(int n) {
low = new int[n];
ord = new int[n];
par = new int[n];
vlis = new int[n];
tr = new int[][](n);
}
}
DFSInfo dfsInfo(T)(T g) {
import std.algorithm : min, each, filter;
import std.conv : to;
const int n = g.length.to!int;
auto info = DFSInfo(n);
with(info) {
int co = 0;
bool[] used = new bool[](n);
void dfs(int p, int b) {
used[p] = true;
low[p] = ord[p] = co++;
par[p] = b;
bool rt = true;
foreach (e; g[p]) {
int d = e.to;
if (rt && d == b) {
rt = false;
continue;
}
if (!used[d]) {
dfs(d, p);
low[p] = min(low[p], low[d]);
} else {
low[p] = min(low[p], ord[d]);
}
}
}
foreach (i; 0..n) {
if (used[i]) continue;
dfs(i, -1);
}
par.filter!"a!=-1".each!((i, v) => tr[v] ~= i.to!int);
ord.each!((i, v) => vlis[v] = i.to!int);
}
return info;
}
Submission Info
Submission Time |
|
Task |
F - Namori |
User |
yosupo |
Language |
D (LDC 0.17.0) |
Score |
2200 |
Code Size |
9289 Byte |
Status |
AC |
Exec Time |
505 ms |
Memory |
30460 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
All |
Score / Max Score |
0 / 0 |
1500 / 1500 |
700 / 700 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt |
Subtask1 |
0_00.txt, 0_01.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt, 2_13.txt, 2_14.txt, 2_15.txt, 2_16.txt, 2_17.txt, 2_18.txt, 2_19.txt, 2_20.txt, 2_21.txt, 2_22.txt, 2_23.txt, 2_24.txt, 2_25.txt, 2_26.txt, 2_27.txt, 2_28.txt, 2_29.txt, 2_30.txt, 2_31.txt, 2_32.txt, 2_33.txt, 2_34.txt, 2_35.txt, 2_36.txt, 2_37.txt, 2_38.txt, 2_39.txt, 2_40.txt, 2_41.txt, 2_42.txt, 2_43.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
AC |
2 ms |
256 KB |
0_01.txt |
AC |
2 ms |
256 KB |
0_02.txt |
AC |
2 ms |
256 KB |
0_03.txt |
AC |
2 ms |
256 KB |
1_00.txt |
AC |
2 ms |
256 KB |
1_01.txt |
AC |
117 ms |
17404 KB |
1_02.txt |
AC |
108 ms |
13564 KB |
1_03.txt |
AC |
98 ms |
12028 KB |
1_04.txt |
AC |
112 ms |
14204 KB |
1_05.txt |
AC |
114 ms |
13948 KB |
1_06.txt |
AC |
114 ms |
13948 KB |
1_07.txt |
AC |
111 ms |
13180 KB |
1_08.txt |
AC |
116 ms |
14460 KB |
1_09.txt |
AC |
106 ms |
11772 KB |
1_10.txt |
AC |
107 ms |
11516 KB |
1_11.txt |
AC |
110 ms |
11516 KB |
1_12.txt |
AC |
112 ms |
11388 KB |
1_13.txt |
AC |
101 ms |
10236 KB |
1_14.txt |
AC |
106 ms |
10748 KB |
1_15.txt |
AC |
112 ms |
11388 KB |
1_16.txt |
AC |
101 ms |
10236 KB |
1_17.txt |
AC |
109 ms |
11388 KB |
2_00.txt |
AC |
2 ms |
256 KB |
2_01.txt |
AC |
503 ms |
30460 KB |
2_02.txt |
AC |
383 ms |
26492 KB |
2_03.txt |
AC |
237 ms |
22652 KB |
2_04.txt |
AC |
462 ms |
26492 KB |
2_05.txt |
AC |
482 ms |
26364 KB |
2_06.txt |
AC |
497 ms |
26364 KB |
2_07.txt |
AC |
475 ms |
26364 KB |
2_08.txt |
AC |
499 ms |
26364 KB |
2_09.txt |
AC |
335 ms |
22268 KB |
2_10.txt |
AC |
389 ms |
22524 KB |
2_11.txt |
AC |
435 ms |
22524 KB |
2_12.txt |
AC |
467 ms |
22652 KB |
2_13.txt |
AC |
108 ms |
10236 KB |
2_14.txt |
AC |
136 ms |
14844 KB |
2_15.txt |
AC |
471 ms |
22780 KB |
2_16.txt |
AC |
101 ms |
10236 KB |
2_17.txt |
AC |
462 ms |
22780 KB |
2_18.txt |
AC |
2 ms |
256 KB |
2_19.txt |
AC |
131 ms |
19708 KB |
2_20.txt |
AC |
111 ms |
15996 KB |
2_21.txt |
AC |
505 ms |
30460 KB |
2_22.txt |
AC |
146 ms |
19324 KB |
2_23.txt |
AC |
143 ms |
19452 KB |
2_24.txt |
AC |
150 ms |
19324 KB |
2_25.txt |
AC |
144 ms |
19452 KB |
2_26.txt |
AC |
146 ms |
19324 KB |
2_27.txt |
AC |
138 ms |
15356 KB |
2_28.txt |
AC |
139 ms |
15228 KB |
2_29.txt |
AC |
135 ms |
15612 KB |
2_30.txt |
AC |
140 ms |
15228 KB |
2_31.txt |
AC |
101 ms |
10236 KB |
2_32.txt |
AC |
144 ms |
15484 KB |
2_33.txt |
AC |
140 ms |
15228 KB |
2_34.txt |
AC |
99 ms |
10236 KB |
2_35.txt |
AC |
141 ms |
15228 KB |
2_36.txt |
AC |
234 ms |
22268 KB |
2_37.txt |
AC |
234 ms |
22268 KB |
2_38.txt |
AC |
234 ms |
22652 KB |
2_39.txt |
AC |
236 ms |
22268 KB |
2_40.txt |
AC |
236 ms |
22652 KB |
2_41.txt |
AC |
234 ms |
22268 KB |
2_42.txt |
AC |
238 ms |
22268 KB |
2_43.txt |
AC |
234 ms |
22268 KB |