Submission #1211019

#TimeUsernameProblemLanguageResultExecution timeMemory
1211019uranium235Zamjene (COCI16_zamjene)Java
140 / 140
1984 ms276400 KiB
//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]; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...