6132

y0shino

k_415

moreexcellent
Everglow_1
dongrq

anonymous233
Susanna

huangbq
Flame_scion

Love_Yourself
tangguochao
にしかた

problem A. Twin Permutations

#include <iostream>

using namespace std;

int main()
{
int T; cin >> T;
while (T --)
{
int n; cin >> n;
for (int i = 0; i < n; i ++)
{
int x; cin >> x;
cout << n - x + 1 << " ";
}
cout << endl;
}
return 0;
}

problem B. Array merging

#include <iostream>
#include <map>

using namespace std;

const int N = 2e5 + 10;
int a[N], b[N];

int main()
{
int T; cin >> T;
while (T --)
{
int n; cin >> n;
map<int, int> m1, m2;
for (int i = 0; i < n; i ++)
{
cin >> a[i];
m1[a[i]] = 1;
}
for (int i = 0; i < n; i ++)
{
cin >> b[i];
m2[b[i]] = 1;
}
for (int i = 0; i < n; i ++)
{
int j = i;
if (a[i] == a[j])
{
while (j < n && a[i] == a[j]) j ++;
m1[a[i]] = max(m1[a[i]], j - i);
i = j - 1;
}
}
for (int i = 0; i < n; i ++)
{
int j = i;
if (b[i] == b[j])
{
while (j < n && b[i] == b[j]) j ++;
m2[b[i]] = max(m2[b[i]], j - i);
i = j - 1;
}
}
int ans = 0;
for (int i = 0; i <= 2 * n; i ++) ans = max(ans, m1[i] + m2[i]);
cout << ans << endl;

}
return 0;
}

problem C. Copil Copac Draws Trees

5
4 5
3 4
2 3
1 2

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10, M = 2 * N;
vector<PII> e[N];
// int e[M], ne[M], h[N], w[M], idx;
int res = 0;

// void add(int a, int b, int c)
// {
//     e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
// }

void dfs(int u, int father, int now, int tot)
{
res = max(res, tot);
for (auto i : e[u])
{
if (i.first == father) continue;
if (i.second < now) dfs(i.first, u, i.second, tot + 1);
else dfs(i.first, u, i.second, tot);
}
// for (int i = h[u]; ~i; i = ne[i])
// {
//     int ver = e[i];
//     if (ver == father) continue;
//     if (w[i] < now) dfs(ver, u, w[i], tot + 1);
//     else dfs(ver, u, w[i], tot);
// }
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
int T; cin >> T;
while (T --)
{
res = 0;
// res = idx = 0;
// memset(h, -1, sizeof h);
int n; cin >> n;
for (int i = 1; i <= n; i ++) e[i].clear();
for (int i = 0; i < n - 1; i ++)
{
int x, y; cin >> x >> y;
e[x].push_back({y, i});
e[y].push_back({x, i});
}
dfs(1, 0, 0, 1);
cout << res << endl;
}
return 0;
}

#include <iostream>
#include <map>

using namespace std;

const int N = 2e5 + 10;
int p[N];
struct Edge
{
int a, b;
}e[N];

int find(int x)
{
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
bool check(int n)
{
for (int i = 1; i <= n; i ++)
{
if (p[i] != 1) return false;
}
return true;
}

int main()
{
int T; cin >> T;
while (T --)
{
int n; cin >> n;
for (int i = 1; i <= n; i ++) p[i] = i;
for (int i = 0; i < n - 1; i ++) cin >> e[i].a >> e[i].b;
int ans = 0;
while (true)
{
if (check(n))
{
cout << ans << endl;
break;
}
bool flag = true;
for (int i = 0; i < n - 1; i ++)
{
int k1 = find(e[i].a), k2 = find(e[i].b);
if (k1 == 1 && k2 == 1) continue;
if (k1 != k2 && (k1 == 1 || k2 == 1))
{
if (k1 == 1) p[k2] = k1;
else p[k1] = k2;
}
}
// for (int i = 1; i <= n; i ++) cout << p[i] << " ";
ans ++;
}

}
return 0;
}

dfs写法

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 2e5 + 10;
vector<int> e[N];
vector<int> a(N), b(N), fa(N), cnt(N), f(N);

void dfs(int u, int father)
{
fa[u] = father;
for(auto i : e[u])
{
if(i == father) continue;
dfs(i, u);
}
}
void dfs1(int u, int father)
{
for(auto i : e[u])
{
if(i == father) continue;
else if(cnt[i] < cnt[u])
{
f[i] = f[u] + 1;
dfs1(i, u);
}
else
{
f[i] = f[u];
dfs1(i, u);
}
}
}

int main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
int T; cin >> T;
while(T --)
{
int n;
cin >> n;
for (int i = 1; i <= n; i ++) e[i].clear();
for(int i = 0; i < n - 1; i ++)
{
int u, v; cin >> u >> v;
a[i] = u, b[i] = v;
e[u].push_back(v);
e[v].push_back(u);
}
fa.clear();
dfs(1, 0);
cnt.clear();
for(int i = 0; i < n - 1; i ++)
{
if(fa[a[i]] == b[i]) swap(a[i], b[i]);
cnt[b[i]] = i;
}
f.clear();
f[1] = 1;
dfs1(1, 0);
int res = 0;
for(int i = 1;i <= n; i ++) res = max(res, f[i]);
cout << res << endl;
}
return 0;
}

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 2e5 + 10, M = 2 * N;
int e[M], ne[M], h[N], idx;
int a[N], b[N], fa[N];
int cnt[N], f[N];

{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u, int father)
{
fa[u] = father;
for (int i = h[u]; ~i; i = ne[i])
{
int ver = e[i];
if (ver == father) continue;
dfs(ver, u);
}
}

void bfs(int u)
{
queue<int> q;
q.push(u);
while (!q.empty())
{
auto t = q.front();
q.pop();
for (int i = h[t]; ~i; i = ne[i])
{
int ver = e[i];
if (f[ver]) continue;
else if (cnt[ver] < cnt[t])
{
f[ver] = f[t] + 1;
q.push(ver);
}
else
{
f[ver] = f[t];
q.push(ver);
}
}
}
}

int main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
int T; cin >> T;
while (T --)
{
idx = 0;
memset(h, -1, sizeof h);
int n; cin >> n;
for (int i = 0; i < n - 1; i ++)
{
cin >> a[i] >> b[i];
}
dfs(1, 0);
for (int i = 0; i < n - 1; i ++)
{
if (fa[a[i]] == b[i]) swap(a[i], b[i]);
cnt[b[i]] = i;
}
memset(f, 0, sizeof f);
f[1] = 1;
bfs(1);
cout << *max_element(f + 1, f + 1 + n) << endl;
}
return 0;
}

problem A. Likes

#include <iostream>
#include <unordered_map>

using namespace std;
const int N = 110;

int main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T --)
{
int n; cin >> n;
unordered_map<int, int> dict;
int cnt1 = 0, cnt2 = 0, cnt3 = 0;
for (int i = 0; i < n; i ++)
{
int x; cin >> x;
if (x > 0)
{
cnt1 ++;
if (dict[x]) cnt3 ++, dict[x] --;
dict[x] = 1;
}
else
{
cnt2 ++;
if (dict[-x]) cnt3 ++, dict[x] --;
dict[-x] = 1;
}

}
for (int i = 1; i <= cnt1; i ++) cout << i << " ";
for (int i = 1; i <= cnt2; i ++) cout << cnt1 - i << " ";
cout << endl;
for (int i = 0; i < cnt3; i ++) cout << 1 << " " << 0 << " ";
for (int i = 1; i <= cnt1 - cnt3; i ++) cout << i << " ";
cout << endl;
}
}

problem B. Settlement of Guinea Pigs

#include <iostream>

using namespace std;
const int N = 1e5 + 10;
int a[N];

int main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T --)
{
int n; cin >> n;
for (int i = 0; i < n; i ++) cin >> a[i];
int pigs = 0, cages = 0, ans = 0;
for (int i = 0; i < n; i ++)
{
if (a[i] == 1)
{
pigs ++;
cages ++;
}
else if (a[i] == 2 && pigs > 0) cages = pigs / 2 + 1;
ans = max(ans, cages);
}
cout << ans << endl;
}
}

problem C. The Very Beautiful Blanket

#include <iostream>

using namespace std;

const int N = 210;

int a[N];

int qmi(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}

int main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
int T;
cin >> T;
while(T --)
{
int n, m;
cin >> n >> m;
cout << n * m << endl;
for(int i = 1;i <= m; i ++)
{
a[i] = i - 1;
cout << a[i] << " ";
}
cout << endl;
for(int i = 2; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
a[j] += qmi(2, 8);
cout << a[j] << " ";
}
cout << endl;
}
}
return 0;
}

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;
typedef pair<int, int> PII;

void solve()
{
int n; cin >> n;
PII a[n + 1];
for (int i = 0; i < n; i ++) cin >> a[i].first >> a[i].second;
sort(a, a + n);
int mx[n + 1];
mx[n - 1] = -2e9;
for (int i = n - 2; i >= 0; i --) mx[i] = max(mx[i + 1], a[i + 1].second);//mx[i]表示i之后b商品的最大值是多少
int ans = 2e9;
set <int> s;
for (int i = 0; i < n; i ++)
{
ans = min(ans, abs(a[i].first - mx[i]));
if (a[i].first > mx[i])
{
// set<int>::iterator it = s.lower_bound(a[i].first);
auto it = s.upper_bound(a[i].first);//才不会告诉你upper_bound和lower_bound其实都可以过
if (it != s.end())   ans = min(ans, *it - a[i].first);//找到set中第一个大于等于a[i].first的更新答案
if (it != s.begin()) ans = min(ans, a[i].first - *(--it));//找到set中第一个小于a[i].first的更新答案
}
s.insert(a[i].second);
}
cout << ans << endl;
}

int main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
int T; cin >> T;
while (T --) solve();

return 0;
}

problem E&&F&&G

1

#include <vector>

1.1 声明

1 vector<int> a //相当于一个长度动态变化的int数组
2 vector<int> a(n)
/**
*跟第一个类似，可以在读入时直接cin >> a[i],
*同时长度为n的数组初始为0，避免在声明局部变量数组的时候需要将所有数组元素初始成0
*vector<int> a(n, x) 表示将长度为n的a[i]赋成x
*/
3 vector<int> a[n] //声明一个一维长n，第二位长度动态变化的int数组
4 struct rec{...} vector<rec> a // 自定义的结构体类型也可以保存在vector中

1.2 主要作用

1 直接当数组用
2 离散化
3 高精度
4 存图
/**
* vector<int> e;
* for (int i = 0; i < n; i ++)
* {
*     int a, b; cin >> a >> b;
*     e[a].push_back(b);
*     e[b].push_back(a);//无向图存储
*  }
*/

1.3 主要函数

vector<int> a;
1 a.size() //返回a中元素数量
2 a.empty() //返回a中是否有元素，若没有返回true，有返回false
3 a.push_back(x) //将x插入a的尾部
4 a.pop_back() //删除a的最后一个元素
5 a.clear() //将a清空，如果a是多维的，需要一维一维清空
6 a.begin() //返回a中第一个元素的迭代器
7 a.end() //返回a的尾部，但注意这是越界访问，相当于访问a[n]，其中n = a.size()
8 a.front() //返回a中的第一个元素，等价于a[0], *a.begin()
9 a.back() //返回a中的最后一个元素，等价于a[n - 1], *(--a.end())，其中n = a.size()

1.4 迭代器

vector的迭代器是“随机访问迭代器”，可以把vector的迭代器与一个整数相加减，其行为和指针的移动类似。

1.5 遍历方式

for (int i = 0; i < a.size(); i ++)
cout << a[i] << endl;

for (vector<int>::iterator it = a.begin(); it != a.end(); it ++)
cout << *it << endl;

2

include <queue>

2.1 声明

queue<int> q;
struct rec{…}; queue<rec> q;
priority_queue<int> q;                              // 大根堆,若在里面存放结构体，需要重新定义小于号
priority_queue<int, vector<int>, greater<int>> q;   // 小根堆，若存放结构体，需要重新定义大于号
priority_queue<pair<int, int>> q;

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
struct e
{
int x, y;
bool operator < (const e & W) const
{
return y < W.y;
}
};

int main()
{
priority_queue<e> q;
q.push({1, 2}), q.push({2, 4});
cout << q.top().y << endl;
}

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
struct e
{
int x, y;
bool operator > (const e & W) const
{
return y > W.y;
}
};

int main()
{
priority_queue<e, vector<e>, greater<e>> q;
q.push({1, 2}), q.push({2, 4});
cout << q.top().y << endl;
}

2.2 主要作用

1 队列主要用于bfs，spfa
2 优先队列中的小根堆用于dijkstra最短路，每次弹出队列中最小的元素
3 大根堆用于一些比较特殊的dijkstra，例如求最大路的时候会用，可参考1026最小花费
4 某些CF上的思维题会用

2.3 主要函数

queue
push    // 从队尾插入
pop     // 从队头弹出
front   // 返回队头元素
back    // 返回队尾元素
priority_queue
push    // 把元素插入堆
pop     // 删除堆顶元素
top     // 查询堆顶元素（最大值）

3

#include <stack>

3.1 主要作用

3.2 主要函数

push    // 向栈顶插入
pop     // 弹出栈顶元素

4

#include <deque>

4.1 主要用途

spfa的SLF优化（只是对数据进行优化，想卡还是可以卡掉）

4.2 主要函数

[]              // 随机访问
begin/end       // 返回deque的头/尾迭代器
front/back      // 队头/队尾元素
push_back       // 从队尾入队
push_front      // 从队头入队
pop_back        // 从队尾出队
pop_front       // 从队头出队
clear           // 清空队列

5

#include <set>

5.1 声明

set<int> s;
struct rec{…}; set<rec> s;  // 结构体rec中必须定义小于号
multiset<double> s;

5.2 主要用途

5.3 主要函数

5.2 size/empty/clear

5.3 迭代器
set和multiset的迭代器称为“双向访问迭代器”，支持星号*解除引用。仅支持++和--两个与算术相关的操作。

5.4 begin/end

s.begin()是指向集合中最小元素的迭代器。

s.end()是指向集合中最大元素的下一个位置的迭代器。换言之，就像vector一样，是一个“前闭后开”的形式。

5.5 insert
s.insert(x)把一个元素x插入到集合s中，时间复杂度为 O(logn)

5.6 find
s.find(x)在集合s中查找等于x的元素，并返回指向该元素的迭代器。若不存在，则返回s.end()。

5.7 lower_bound/upper_bound

s.lower_bound(x)查找大于等于x的元素中最小的一个，并返回指向该元素的迭代器。

s.upper_bound(x)查找大于x的元素中最小的一个，并返回指向该元素的迭代器。

5.8 erase

5.9 count
s.count(x)返回集合s中等于x的元素个数，时间复杂度为 O(k+logn)，其中 k 为元素x的个数。

6

#include <map>

map容器是一个键值对key-value的映射，其内部实现是一棵以key为关键码的红黑树。Map的key和value可以是任意类型，其中key必须定义小于号运算符。
6.1 声明

map<key_type, value_type> name;

//例如：
map<long long, bool> vis;
map<string, int> hash;
map<pair<int, int>, vector<int>> test;

6.2 主要作用

1 记录路径，例如提高课中的八数码
2 思维题

6.3 主要函数

6.2 size/empty/clear/begin/end

6.3 insert/erase

6.4 find
h.find(x)在变量名为h的map中查找key为x的二元组。

6.5 []操作符
h[key]返回key映射的value的引用，时间复杂度为 O(logn)

[]操作符是map最吸引人的地方。我们可以很方便地通过h[key]来得到key对应的value。

7

#include <unordered_map>

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int N = 1010, M = 5010;
int f[N];
int e[M], ne[M], h[N], w[M], idx;
double dist[N];
int cnt[N];
bool st[N];
int n, m;

void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

bool check(double mid)
{
queue<int> q;
for (int i = 1; i <= n; i ++)
{
cnt[i] = 0;
q.push(i);
st[i] = true;
}
while (!q.empty())
{
auto t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int ver = e[i];
double x = w[i] * mid - f[t];
if (dist[ver] > dist[t] + x)
{
dist[ver] = dist[t] + x;
cnt[ver] = cnt[t] + 1;
if (cnt[ver] >= n) return true;
if (!st[ver])
{
st[ver] = true;
q.push(ver);
}
}
}
}
return false;
}

int main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
memset(h, -1, sizeof h);
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> f[i];
while (m --)
{
int a, b, c; cin >> a >> b >> c;
}
double l = 0, r = 1e6, eps = 1e-4;
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
printf("%.2lf", l);
return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 510, M = 5210;
int e[M], ne[M], h[N], w[M], idx;
int dist[N], cnt[N];
bool st[N];
int n, m1, m2;

void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

bool spfa()
{
memset(cnt, 0, sizeof cnt);
memset(st, 0, sizeof st);
memset(dist, 0x3f, sizeof dist);
queue<int> q;
for (int i = 1; i <= n; i ++)
{
q.push(i);
st[i] = true;
}
while (!q.empty())
{
auto t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int ver = e[i];
if (dist[ver] > dist[t] + w[i])
{
dist[ver] = dist[t] + w[i];
cnt[ver] = cnt[t] + 1;
if (cnt[ver] >= n) return true;
if (!st[ver])
{
q.push(ver);
st[ver] = true;
}
}
}
}
return false;
}

int main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
int T; cin >> T;
while (T --)
{
memset(h, -1, sizeof h);
idx = 0;
cin >> n >> m1 >> m2;
while (m1 --)
{
int a, b, c; cin >> a >> b >> c;
}
while (m2 --)
{
int a, b, c; cin >> a >> b >> c;
}
if (spfa()) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}

problem A 最小的数字

#include <iostream>

using namespace std;

int main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
int n; cin >> n;
int k = n / 3;
if (n % 3 == 0) cout << k * 3 << endl;
else cout << k * 3 + 3 << endl;
return 0;
}

problem B 优美的GCD

#include <iostream>

using namespace std;

int main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
int T; cin >> T;
while (T --)
{
int n; cin >> n;
cout << n << " " << 2 * n << endl;
}
return 0;
}

problem C 优美的序列

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010;
int a[N];

int main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
int T; cin >> T;
while (T --)
{
int n; cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
sort(a + 1, a + n + 1);
bool suc = true;
for (int i = 1; i <= n; i ++)
{
for (int j = i; j <= n; j ++)
{
if (abs(a[i] - a[j]) < abs(i - j))
{
suc = false;
break;
}
}
if (!suc) break;
}
if (suc) for (int i = 1; i <= n; i ++) cout << a[i] << " ";
else cout << -1;
cout << endl;
}
return 0;
}

problem D&E Kevin喜欢零

#include <iostream>
#include <algorithm>
#define int long long

using namespace std;
const int N = 2e5 + 10;
int n, k;
int a[N];
int ca[N], cb[N];
void solve()
{
cin >> n >> k;
for(int i = 0; i <= n; i ++) ca[i] = cb[i] = 0;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++)
{
int u = a[i];
while(u % 2 == 0) u /= 2, ca[i] ++;
while(u % 5 == 0) u /= 5, cb[i] ++;
}
for(int i = 1; i <= n; i ++)
{
ca[i] += ca[i - 1];
cb[i] += cb[i - 1];
}
int ans = 0;
// for (int i = 1; i <= n; i ++) cout << ca[i] << " ";
// cout << endl;
// for (int i = 1; i <= n; i ++) cout << cb[i] << " ";
// cout << endl;
//注意这里前缀和一定是单调递增的，因此必定存在r>=l
for(int l = 1; l <= n; l ++)
{
int v1 = k + ca[l - 1];//将前一个枚举的边界除去,这里通过让k + ca, k + cb除去,其实和除一个数就在另一边乘这个数是一个道理
int v2 = k + cb[l - 1];
int l1 = lower_bound(ca + 1, ca + 1 + n, v1) - ca;//找到大于等于v1的第一个下标
// cout << "l1 = " << l1 << "  " << v1 << endl;
int r1 = upper_bound(ca + 1, ca + 1 + n, v1) - ca - 1;
// cout << "r1 = " << r1 << endl;
//upper_bound用于找到大于v1的第一个数，-1作用在于找到小于等于v1的最后一个下标
int l2 = lower_bound(cb + 1, cb + 1 + n, v2) - cb;//找到大于等于v2的第一个下标
int r2 = upper_bound(cb + 1, cb + 1 + n, v2) - cb - 1;//找到小于等于v2的最后一个下标
// cout << "l2 = " << l2 << "  " << v2 << endl;
// cout << "r2 = " << r2 << endl;
int L = max(l1, l2);
int R = max(r1, r2);
// cout << "L = " << L << " " << " R = " << R << endl;
if(L > R) continue;//说明L越界了，此处也可以写成L == n + 1
L = max(L, l);
ans += (R - L + 1);
// cout << "ans = " << ans << endl;
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
int T; cin >> T;
while(T --) solve();
return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long

using namespace std;

const int N = 510, M = 1e4 + 10;
struct Edge
{
int x, y, w;
bool f;
bool operator < (const Edge &W) const
{
return w < W.w;
}
}edges[M];
int p[N];
int dist1[N][N], dist2[N][N];
int e[2 * M], ne[2 * M], w[2 * M], h[N], idx;
int n, m;

void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

int find(int x)
{
if (x != p[x] && p[x] != p[p[x]]) p[x] = find(p[x]);
return p[x];
}

void dfs(int u, int fa, int maxd1, int maxd2, int d1[], int d2[])
{
d1[u] = maxd1, d2[u] = maxd2;
for (int i = h[u]; ~i; i = ne[i])
{
int ver = e[i];
if (ver != fa)
{
int td1 = maxd1, td2 = maxd2;
if (w[i] > td1) td2 = td1, td1 = w[i];
else if (w[i] < td1 && w[i] > td2) td2 = w[i];
dfs(ver, u, td1, td2, d1, d2);
}
}
}

signed main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++) p[i] = i;
for (int i = 0; i < m; i ++) cin >> edges[i].x >> edges[i].y >> edges[i].w;
sort(edges, edges + m);
int sum = 0;
for (int i = 0; i < m; i ++)
{
int k1 = find(edges[i].x), k2 = find(edges[i].y);
if (k1 != k2)
{
p[k1] = k2;
sum += edges[i].w;
edges[i].f = true;
}
}
for (int i = 1; i <= n; i ++) dfs(i, -1, -1e9, -1e9, dist1[i], dist2[i]);
int res = 1e18;
for (int i = 0; i < m; i ++ )
{
if (!edges[i].f)
{
int a = edges[i].x, b = edges[i].y, w = edges[i].w;
int t;
if (w > dist1[a][b])
t = sum + w - dist1[a][b];
else if (w > dist2[a][b])
t = sum + w - dist2[a][b];
res = min(res, t);
}
}
cout << res << endl;
return 0;
}

problem A. Grasshopper on a Line

#include <iostream>

using namespace std;

int main()
{
int T; cin >> T;
while (T --)
{
int n, k; cin >> n >> k;
if (n % k)
{
cout << 1 << endl;
cout << n << endl;
}
else
{
cout << 2 << endl;
cout << n - 1 << " " << 1 << endl;
}
}
return 0;
}

problem B. Comparison String

#include <iostream>

using namespace std;

int main()
{
int T; cin >> T;
while (T --)
{
int n; cin >> n;
string str; cin >> str;
int cnt1 = 0, cnt2 = 0;
for (int i = 0; i < n; )
{
if (str[i] == '>')
{
int cnt3 = 0;
while (i < n && str[i] == '>') i ++, cnt3 ++;
cnt1 = max(cnt1, cnt3);
}
else
{
int cnt4 = 0;
while (i < n && str[i] == '<') i ++, cnt4 ++;
cnt2 = max(cnt2, cnt4);
}
}
cout << max(cnt1, cnt2) + 1 << endl;
}
return 0;
}

problem C. Best Binary String

#include <iostream>

using namespace std;

int main()
{
int T; cin >> T;
while (T --)
{
string str; cin >> str;
int flag = 0;
for (int i = 0; i < str.size(); i ++)
{
if (str[i] == '0')
{
flag = 0;
cout << (char)str[i];
}
else if (str[i] == '1')
{
flag = 1;
cout << (char)str[i];
}
else cout << (char)(flag + '0');
}
cout << endl;
}
return 0;
}

problem D. Bracket Coloring

#include <iostream>

using namespace std;
const int N = 2e5 + 10;

int ans[N];

int main()
{
int T; cin >> T;
while(T --)
{
int n; cin >> n;
string s; cin >> s;
int cnt = 0, k = 0, lst = 0;
for(int i = 0; i < n; i ++)
{
if(s[i] == s[0]) cnt ++;
else cnt --;
if(lst + cnt > 0) ans[i] = 1;
else ans[i] = 2;
k = max(k, ans[i]);
lst = cnt;
}
if(cnt != 0)
{
cout << -1 << endl;
continue;
}
cout << k << endl;
for(int i = 0; i < n; i ++) cout << ans[i] << " ";
cout << endl;
}
return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 6010, M = N * N / 2;
struct Edge
{
int x, y, w;
bool operator < (const Edge &W) const
{
return w < W.w;
}
}e[M];

int p[N], sz[N];
int n;

int find(int x)
{
if (x != p[x] && p[x] != p[p[x]]) p[x] = find(p[x]);
return p[x];
}

int kruskal()
{
sort(e, e + n - 1);
int res = 0;
for (int i = 0; i < n - 1; i ++)
{
int k1 = find(e[i].x), k2 = find(e[i].y);
if (k1 != k2)
{
res += (sz[k1] * sz[k2] - 1) * (e[i].w + 1);
sz[k2] += sz[k1];
p[k1] = k2;
}
}
return res;
}

int main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
int T; cin >> T;
while (T --)
{
cin >> n;
for (int i = 0; i < n - 1; i ++) cin >> e[i].x >> e[i].y >> e[i].w;
for (int i = 1; i <= n; i ++) p[i] = i, sz[i] = 1;
int ans = kruskal();
cout << ans << endl;
}
return 0;
}

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 510, M = N * N;
typedef pair<int, int> PII;
struct Edge
{
int x, y;
double w;
bool operator < (const Edge &W) const
{
return w < W.w;
}
}e[M];
PII q[N];
int p[N];
int n, k, cnt;

double get_dist(PII a, PII b)
{
int x = a.first - b.first;
int y = a.second - b.second;
return sqrt(x * x + y * y);
}

int find(int x)
{
if (x != p[x] && p[x] != p[p[x]]) p[x] = find(p[x]);
return p[x];
}

double kruskal()
{
sort(e, e + cnt);
double res = 0;
for (int i = 0; i < cnt; i ++)
{
if (n <= k) break;
int k1 = find(e[i].x), k2 = find(e[i].y);
if (k1 != k2)
{
res = e[i].w;
p[k1] = k2;
n --;
}
}
return res;
}

int main()
{
cin >> n >> k;
for (int i = 0; i <= n; i ++) p[i] = i;
for (int i = 0; i < n; i ++) cin >> q[i].first >> q[i].second;
for (int i = 0; i < n; i ++)
for (int j = 0; j < i; j ++)
e[cnt ++] = {i, j, get_dist(q[i], q[j])};
double ans = kruskal();
printf("%.2lf\n", ans);
return 0;
}