Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.StringTokenizer;
- import java.io.BufferedReader;
- import java.io.BufferedOutputStream;
- import java.io.IOException;
- import java.io.InputStream;
- import java.io.InputStreamReader;
- import java.io.PrintWriter;
- import java.io.OutputStream;
- class Kattio extends PrintWriter {
- public Kattio(InputStream i) {
- super(new BufferedOutputStream(System.out));
- r = new BufferedReader(new InputStreamReader(i));
- }
- public Kattio(InputStream i, OutputStream o) {
- super(new BufferedOutputStream(o));
- r = new BufferedReader(new InputStreamReader(i));
- }
- public int getInt() {
- return Integer.parseInt(nextToken());
- }
- public double getDouble() {
- return Double.parseDouble(nextToken());
- }
- public long getLong() {
- return Long.parseLong(nextToken());
- }
- public String getWord() {
- return nextToken();
- }
- private BufferedReader r;
- private String line;
- private StringTokenizer st;
- private String token;
- private String peekToken() {
- if (token == null)
- try {
- while (st == null || !st.hasMoreTokens()) {
- line = r.readLine();
- if (line == null) return null;
- st = new StringTokenizer(line);
- }
- token = st.nextToken();
- } catch (IOException e) { }
- return token;
- }
- private String nextToken() {
- String ans = peekToken();
- token = null;
- return ans;
- }
- }
- class UnionFind {
- int[] p;
- int[] rank;
- boolean[] open;
- int[] end;
- //1 based indexing!!!!
- UnionFind(int n) {
- p = new int[n+1];
- rank = new int[n+1];
- end = new int[n+1];
- open = new boolean[n+1];
- for (int i = 1; i < n+1; i++) {
- p[i] = i;
- rank[i] = 0;
- end[i] = 0;
- open[i] = true;
- }
- }
- int findset (int i) {
- if (p[i] == i) {return i;}
- else {
- p[i] = findset(p[i]);
- return p[i];
- }
- }
- void closeset (int i) {
- open[findset(i)] = false;
- }
- boolean issetopen (int i) {
- return open[findset(i)];
- }
- boolean issameset(int i, int j) {
- return findset(i) == findset(j);
- }
- //adding left to right, right end preserved
- void unionset (int i, int j) {
- if (!issameset(i, j)) {
- int x = findset(i), y = findset(j);
- if (!open[x] || !open[y]) {
- open[x] = false;
- open[y] = false; //i can put a marker and then
- //change one value only but
- //this is okay also
- }
- else {
- end[x] = end[y]; //free end node only left for open + open
- }
- if (rank[x] > rank[y]) p[y] = x;
- else {
- p[x] = y;
- if (rank[x] == rank[y]) rank[y] += 1;
- }
- }
- else {open[findset(i)] = false;}
- }
- }
- public class Ladice {
- public static void main(String[] args) {
- Kattio br = new Kattio(System.in);
- int n1 = br.getInt(), n2 = br.getInt();
- boolean[] occupied = new boolean[n2 + 1];
- UnionFind u = new UnionFind(n2);
- for (int i = 0; i < n1; i++) {
- int a = br.getInt(), b = br.getInt();
- if (!occupied[a]) {
- occupied[a] = true;
- u.unionset(a, b);
- br.println("LADICA");
- }
- else if (!occupied[b]) {
- occupied[b] = true;
- u.unionset(b, a);
- br.println("LADICA");
- }
- else if (u.issetopen(a)) {
- occupied[u.end[a]] = true;
- u.unionset(a, b);
- br.println("LADICA");
- }
- else if (u.issetopen(b)) {
- occupied[u.end[b]] = true;
- u.unionset(b, a);
- br.println("LADICA");
- }
- else {br.println("SMECE");}
- }
- br.close();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement