You are not logged in. Please login at www.codechef.com to post your questions!

×

# FillMTR Solution not passing with DSU

 0 1 My following code is giving wrong answer constantly. Please help me. I have used approach of DSU and assigning color to root and comparing color of root while union. If anyone got Ac, with this approach,Please give link of code. import java.io.; import java.math.; import java.util.*; import static java.util.Arrays.fill; import static java.lang.Math.*; import static java.util.Arrays.sort; import static java.util.Collections.sort; class FillTheMatrix { public static int mod = 1000000007; static FasterScanner in = new FasterScanner(); static PrintWriter out = new PrintWriter(System.out); static int maxn=(int) (1e5+2); static int[] parent=new int[maxn]; static int[] size=new int[maxn]; static int[] color=new int[maxn]; public static int findheadof(int x) { while(x!=parent[x]) { parent[x]=parent[parent[x]]; x=parent[x]; } return x; } public static void union(int u,int v) { int x=findheadof(u); int y=findheadof(v); if(x==y) return; if(size[x]0) { int n=in.nextInt(); int q=in.nextInt(); for(int i=1;i<=n;i++) { parent[i]=i; size[i]=1; color[i]=2; //color ==2 means no color } boolean ispossible=true; while(q-->0) { int u=in.nextInt(); int v=in.nextInt(); int w=in.nextInt(); if(u==v) { if(w!=0) ispossible=false; continue; } if(w==0) { if(color[findheadof(u)]!=2 && color[findheadof(v)]!=2) { if(color[findheadof(u)]!=color[findheadof(v)]) ispossible=false; } if(color[findheadof(u)]==2 && color[findheadof(v)]==2) { union(u, v); color[u]=0; color[v]=0; continue; } if(findheadof(u)==u && size[findheadof(u)]==1) { union(u, v); color[u]=color[findheadof(v)]; continue; } if(findheadof(v)==v && size[findheadof(v)]==1) { union(u, v); color[v]=color[findheadof(u)]; } } else { if(color[findheadof(u)]!=2 && color[findheadof(v)]!=2) { if(color[findheadof(u)]==color[findheadof(v)]) ispossible=false; } if(color[findheadof(u)]==2 && color[findheadof(v)]==2) { color[findheadof(v)]=1; } if(findheadof(u)==u && size[findheadof(u)]==1 && color[findheadof(u)]==2) { color[u]=1-color[findheadof(v)]; continue; } if(findheadof(v)==v && size[findheadof(v)]==1) { color[v]=1-color[findheadof(u)]; } } } if(ispossible) out.println("yes"); else out.println("no"); } out.close(); } public static long pow(long x, long n, long mod) { long res = 1; for (long p = x; n > 0; n >>= 1, p = (p * p) % mod) { if ((n & 1) != 0) { res = (res * p % mod); } } return res; } public static long gcd(long n1, long n2) { long r; while (n2 != 0) { r = n1 % n2; n1 = n2; n2 = r; } return n1; } static class FasterScanner { private byte[] buf = new byte[1024]; private int curChar; private int snumChars; public int read() { if (snumChars == -1) throw new InputMismatchException(); if (curChar >= snumChars) { curChar = 0; try { snumChars = System.in.read(buf); } catch (IOException e) { throw new InputMismatchException(); } if (snumChars <= 0) return -1; } return buf[curChar++]; } public String nextLine() { int c = read(); while (isSpaceChar(c)) c = read(); StringBuilder res = new StringBuilder(); do { res.appendCodePoint(c); c = read(); } while (!isEndOfLine(c)); return res.toString(); } public String nextString() { int c = read(); while (isSpaceChar(c)) c = read(); StringBuilder res = new StringBuilder(); do { res.appendCodePoint(c); c = read(); } while (!isSpaceChar(c)); return res.toString(); } public long nextLong() { int c = read(); while (isSpaceChar(c)) c = read(); int sgn = 1; if (c == '-') { sgn = -1; c = read(); } long res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res *= 10; res += c - '0'; c = read(); } while (!isSpaceChar(c)); return res * sgn; } public int nextInt() { int c = read(); while (isSpaceChar(c)) c = read(); int sgn = 1; if (c == '-') { sgn = -1; c = read(); } int res = 0; do { if (c < '0' || c > '9') throw new InputMismatchException(); res *= 10; res += c - '0'; c = read(); } while (!isSpaceChar(c)); return res * sgn; } public int[] nextIntArray(int n) { int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = nextInt(); } return arr; } public long[] nextLongArray(int n) { long[] arr = new long[n]; for (int i = 0; i < n; i++) { arr[i] = nextLong(); } return arr; } private boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } private boolean isEndOfLine(int c) { return c == '\n' || c == '\r' || c == -1; } }  } asked 19 Sep '17, 13:25 12●3 accept rate: 0%

One Answer:
 0 I used DSU and colour too in order to solve it. Here's the link to my AC : link. But I used the property of 2 colour(i.e. Suppose the colour of set $S_1$ is white, colour of $S_2$ must be black and so on). I know I am bad at explaining. Hope you get it!! Also I learned this from this video! answered 19 Sep '17, 14:00 614●1●9 accept rate: 12% Can u explain your code? What is the purpose of bfs? (19 Sep '17, 15:27) Consider disjoint sets $S_1$ as {a,b,c} , $S_2$ as {x,y,z} and $S_3$ as {p,q,r}. How did I partition this disjoint sets? The nodes having difference 0 are clubbed into a set. Hence, nodes of $S_1$ have 0 difference in value and similarly for $S_2$ and $S_3$. Now, what bfs(probably it is dfs but I mistakenly wrote it as bfs :P) does is that it colours all elements of set with same colour. For example, if you pass a and white in bfs function, it will set all elements of Set $S_1$ to white because obviously their colours must be same. Hope this clears your doubt! (19 Sep '17, 15:41)
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• link:[text](http://url.com/ "title")
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×286
×67
×57
×23
×16
×15
×7

question asked: 19 Sep '17, 13:25

question was seen: 346 times

last updated: 19 Sep '17, 15:42