# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
997431 | Trisanu_Das | Magic Show (APIO24_show) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "Alice.h"
#include <bits/stdc++.h>
using namespace std;
// you may define some global variables, but it does not work if you try to transfer any information from function Alice() to function Bob() through these variables.
// you had better not use the same global variables in function Alice() and in function Bob().
long long par[5000];
long long find(long long x) {
if(x == par[x]) {
return x;
}
return find(par[x]);
}
void unite(long long a, long long b) {
a = find(a);
b = find(b);
if(a == b) return;
par[a] = b;
}
vector<pair<int,int> > Alice() {
// add your code here
// change below into your code
iota(par, par + 5000, 0);
long long x = setN(5000);
long long center1 = (x - 1) / 5000;
long long center2 = (x - 1) % 5000;
long long center3 = (center2 - center1 + 5000) % 5000;
vector<pair<int, int> > edges;
for(long long i = 0; i < 1667; i++) {
if(center1 != i) {
if(find(center1) != find(i)) {
edges.push_back({center1 + 1, i + 1});
unite(i, center1);
}
}
}
for(long long i = 1667; i < 3334; i++) {
if(center2 != i) {
if(find(center2) != find(i)) {
edges.push_back({center2 + 1, i + 1});
unite(i, center2);
}
}
}
for(long long i = 3334; i < 5000; i++) {
if(center3 != i) {
if(find(center3) != find(i)) {
edges.push_back({center3 + 1, i + 1});
unite(i, center3);
}
}
}
long long prev_same = -1;
for(long long i = 0; i < 5000; i++) {
if(find(i) == i) {
if(prev_same != -1) {
edges.push_back({prev_same + 1, i + 1});
}
prev_same = i;
}
}
return edges;
}