[problem:451364A]
Idea: yazan_istatiyeh, prepared: noomaK
This problem was our way of saying hi:)
To solve the problem you can keep increasing n until it is divisible by k, this is a linear solution.
A constant solution is to find how much we need to add to n to make it divisible by k, so the solution becomes $$$x + k - (x \pmod k)$$$, or $$$(n / k + 1) * k$$$ taking advantage of integer (floor) division.
[problem:451364B]
Idea: DeadPixel99, prepared: noomaK
[problem:451364C]
Idea: noomaK, prepared: noomaK
[problem:451364D]
Idea: noomaK, prepared: noomaK
[problem:451364E]
Idea: noomaK, prepared: yazan_istatiyeh
Connecting and disconnecting roads gives a hint to using DSU, also finding the minimum number of coins gives a hint to binary search.
The first thing we notice is that blocking all roads would be valid, now to construct the solution, we will use binary search on the answer, it will work because if we blocked all roads that cost $$$X$$$ or less and it was valid, blocking all roads that cost $$$X + 1$$$ or less would be valid too.
So for each midpoint in the binary search, we can check if the current cost is valid or not by connecting components in DSU when an edge cost is more than the current cost we are checking (the more we block the better, so we should not be choosy about what to block or not, if we can block a road then it is either would not change anything or it would disconnect two cities from each other), after that, we can check for connectivity for all forbidden pairs (cities in feuds), if all pairs were disconnected, then the current cost is valid and we search for less, if not, the current cost is invalid and we should search for a higher cost.
Solution Complexity: $$$O(log_2(10 ^ 9) * m * log_2(n))$$$
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
class UnionFind {
private:
vector<int> p, rank, setSize;
int numSets;
public:
UnionFind(int N) {
p.assign(N, 0);
for (int i = 0; i < N; i++) {
p[i] = i;
}
rank.assign(N, 0);
setSize.assign(N, 1);
numSets = N;
}
int findSet(int i) {
return (p[i] == i) ? i : (p[i] = findSet(p[i]));
}
bool isSameSet(int i, int j) {
return findSet(i) == findSet(j);
}
int numDisjointSets() {
return numSets;
}
int sizeOfSet(int i) {
return setSize[findSet(i)];
}
void unionSet(int i, int j) {
if (isSameSet(i, j)) return;
int x = findSet(i), y = findSet(j);
if (rank[x] > rank[y]) swap(x, y);
p[x] = y;
if (rank[x] == rank[y]) rank[y]++;
setSize[y] += setSize[x];
numSets--;
}
};
struct Edge {
int u, v, t;
Edge(int u, int v, int t): u(u), v(v), t(t) {}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<Edge> edges;
for (int i = 0; i < m; i++) {
int u, v, t;
cin >> u >> v >> t;
u--, v--;
edges.emplace_back(u, v, t);
}
vector<pair<int, int>> feuds(k);
for (auto &[u, v]: feuds) {
cin >> u >> v;
u--, v--;
}
auto check = [&](int x) {
UnionFind dsu(n);
for (auto [u, v, t]: edges) {
if (t > x) dsu.unionSet(u, v);
}
for (auto [u, v]: feuds) {
if (dsu.isSameSet(u, v)) {
return false;
}
}
return true;
};
int l = 0, r = 1e9, ans = 1e9;
while (l <= r) {
int mid = l + (r - l) / 2;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << ans;
}
[problem:451364F]
Idea: yazan_istatiyeh & noomaK, prepared: yazan_istatiyeh
The solution uses trie with pointers, by yazan_istatiyeh:
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
class Trie {
private:
struct Node {
char alphabet;
bool exist; // or end of word, or count of words
int cnt;
vector<Node*> child;
Node(char a): alphabet(a), exist(false), cnt(0) {
child.assign(26, NULL);
}
};
Node* root;
public:
Trie() {
root = new Node('!');
}
void insert(string word) {
Node* cur = root;
for (int i = 0; i < (int) word.size(); i++) {
int alphaNum = word[i] - 'a';
if (cur -> child[alphaNum] == NULL) {
cur -> child[alphaNum] = new Node(word[i]);
}
cur = cur -> child[alphaNum];
}
cur -> exist = true;
}
ll getAns() {
function<void(Node*)> dfs = [&](Node* node) {
node->cnt = node->exist;
for (auto next: node->child) {
if (next != NULL) {
dfs(next);
node->cnt += next->cnt;
}
}
};
dfs(root);
ll ret = 0;
function<void(Node*, int)> calc = [&](Node* node, int depth) {
ll pre = 0;
for (int i = 0; i < 26; i++) {
if (node->child[i] == NULL) continue;
auto &next = node->child[i];
ret += node->exist * depth * next->cnt;
ret += pre * depth * next->cnt;
pre += next->cnt;
calc(next, depth + 1);
}
};
calc(root, 0);
return ret;
}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
Trie trie;
ll ans = 0;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
trie.insert(s);
ans += (2ll * n - 2) * s.size();
}
ans -= trie.getAns() * 4;
cout << ans;
}
This solution uses trie with normal arrays, by noomaK:
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int N = 1e6 + 1;
const int K = 26;
int trie[N + 2][K];
int sub[N + 5];
int tc;
void insert(const string &s) {
int n = s.size();
int root = 0;
for (int i = 0; i < n; ++i) {
int j = s[i] - 'a';
if (!trie[root][j]) {
trie[root][j] = ++tc;
}
root = trie[root][j];
}
sub[root] += 1;
}
ll ans;
string cr;
void dfs(int u, int d = 0) {
ll cur = sub[u], sum = 0;
string t = cr;
for (int j = 0; j < 26; ++j) if (trie[u][j]) {
int v = trie[u][j];
dfs(v, d + 1);
sub[u] += sub[v];
sum += cur * sub[v];
cur += sub[v];
}
ans -= d * 4ll * sum;
}
void solve() {
int n;
cin >> n;
ans = tc = 0;
for (int i = 0; i < n; ++i) {
string s;
cin >> s;
insert(s);
ans += (n - 1) * 2ll * (int)s.size();
}
dfs(0);
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while(t--) {
solve();
}
}
[problem:451364G]
Idea: noomaK, prepared: noomaK
