Submission #1211019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211019		uranium235	Zamjene (COCI16_zamjene)	Java	140 / 140	1984 ms	276400 KiB

zamjene

//package ojuz;

import java.io.*;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;

public class zamjene {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] first = reader.readLine().split(" ");
        int n = Integer.parseInt(first[0]), q = Integer.parseInt(first[1]);

        DSU dsu = new DSU(n, Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).map(i -> i - 1).toArray());

        for (int i = 0; i < q; i++) {
            String[] query = reader.readLine().split(" ");
            int type = Integer.parseInt(query[0]);
            if (type == 1) {
                int a = Integer.parseInt(query[1]) - 1, b = Integer.parseInt(query[2]) - 1;
                int aRoot = dsu.find(a), bRoot = dsu.find(b);
                if (aRoot != bRoot) {
                    dsu.ungood(aRoot);
                    dsu.ungood(bRoot);
                    dsu.remove(aRoot);
                    dsu.remove(bRoot);
                    // remove the two elements
                    dsu.hashCurrent[aRoot] -= dsu.rng[dsu.a[a]];
                    dsu.hashCurrent[bRoot] -= dsu.rng[dsu.a[b]];
                    // add them back
                    dsu.hashCurrent[aRoot] += dsu.rng[dsu.a[b]];
                    dsu.hashCurrent[bRoot] += dsu.rng[dsu.a[a]];
                    dsu.good(aRoot);
                    dsu.good(bRoot);
                    dsu.add(aRoot);
                    dsu.add(bRoot);
                }
                // swap the elements
                int temp = dsu.a[a];
                dsu.a[a] = dsu.a[b];
                dsu.a[b] = temp;
            } else if (type == 2) {
                int a = Integer.parseInt(query[1]) - 1, b = Integer.parseInt(query[2]) - 1;
                dsu.unite(a, b);
            } else if (type == 3) {
                writer.write(dsu.good == dsu.groups ? "DA" : "NE");
                writer.newLine();
            } else {
                writer.write(String.valueOf(dsu.ans));
                writer.newLine();
            }

        }
        writer.flush();
    }

    static class DSU {
        // multiset of hashCurrent[i] - hashSorted[i]
        // this probably doesnt need to be a multiset, except for 0
        public final Map<Long, Integer> freq = new HashMap<>();
        public final int[] p, a, sorted, sz;
        public final long[] hashCurrent, hashSorted, rng;
        public long ans;
        public int good, groups;
        public DSU(int n, int[] a) {
            this.a = a;
            int[] temp = a.clone();
            Arrays.sort(temp);
            this.sorted = temp;
            this.p = new int[n];
            Arrays.setAll(p, i -> i);
            this.hashCurrent = new long[n];
            this.hashSorted = new long[n];
            this.rng = new long[1_000_000];
            Arrays.setAll(rng, i -> ThreadLocalRandom.current().nextLong());
            Arrays.setAll(hashCurrent, i -> rng[a[i]]);
            Arrays.setAll(hashSorted, i -> rng[sorted[i]]);
            this.sz = new int[n];
            Arrays.fill(this.sz, 1);
            for (int i = 0; i < n; i++) {
                good(i);
                add(i);
            }
            this.groups = n;
        }

        public int find(int i) {
            return p[i] == i ? i : (p[i] = find(p[i]));
        }

        public void unite(int a, int b) {
            if ((a = find(a)) == (b = find(b))) return;
            if (sz[a] > sz[b]) {
                unite(b, a);
                return;
            }

            ungood(a);
            ungood(b);
            remove(a);
            remove(b);
            p[a] = b;
            // hashCurrent will be modified by the main code
            hashCurrent[b] += hashCurrent[a];
            hashSorted[b] += hashSorted[a];
            sz[b] += sz[a];
            groups--;
            good(b);
            add(b);
        }

        public void good(int i) {
            if (hashSorted[i] == hashCurrent[i]) good++;
        }

        public void ungood(int i) {
            if (hashSorted[i] == hashCurrent[i]) good--;
        }

        public void remove(int i) {
            long key = hashCurrent[i] - hashSorted[i];
            if (key == 0) return;
            freq.merge(key, -sz[i], Integer::sum);
            ans -= (long) freq.getOrDefault(-key, 0) * sz[i];
        }

        public void add(int i) {
            long key = hashCurrent[i] - hashSorted[i];
            if (key == 0) return;
            freq.merge(key, sz[i], Integer::sum);
            ans += (long) freq.getOrDefault(-key, 0) * sz[i];
        }
    }
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14