#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
using namespace std;
using pi = pair<int, int>;
const int MAXN = (int)(7e4) + 5;
vector<int> adj[MAXN];
int par[MAXN];
set<int> minc[MAXN];
set<int> maxc[MAXN];
vector<int> color[MAXN];
vector<int> to[MAXN];
bool visited[MAXN];
int deg[MAXN];
unordered_map<int, int> condense;
int rev[MAXN];
void merge(pi& x, pi& y) {
if (minc[x.first].size() < minc[y.first].size()) {
swap(x.first, y.first);
}
if (maxc[x.second].size() < minc[y.second].size()) {
swap(x.second, y.second);
}
for (int i : minc[y.first]) {
if (minc[x.first].count(i)) {
minc[x.first].erase(i);
}
else {
minc[x.first].insert(i);
}
}
for (int i : maxc[y.second]) {
if (maxc[x.second].count(i)) {
maxc[x.second].erase(i);
}
else {
maxc[x.second].insert(i);
}
}
if (minc[y.first].size()<5) {
minc[y.first].clear();
}
if (maxc[y.second].size() < 5) {
maxc[y.second].clear();
}
}
pi root(int n, int p) {
pi cur = {n, n};
par[n] = p;
for (int e : adj[n]) {
if (e != p) {
pi d = root(e, n);
merge(cur, d);
}
}
if (minc[cur.first].size() > 0) {
int z = *(minc[cur.first].rbegin());
if (!condense.count(z)) {
rev[condense.size()] = z;
condense[z] = condense.size();
}
color[condense[z]].push_back(n);
to[n].push_back(condense[z]);
}
if (maxc[cur.second].size() > 0) {
int z = *(maxc[cur.second].begin());
if (!condense.count(z)) {
rev[condense.size()] = z;
condense[z] = condense.size();
}
color[condense[z]].push_back(n);
to[n].push_back(condense[z]);
}
return cur;
}
int main()
{
// freopen("input.in", "r", stdin);
cin.tie(0);
cin.sync_with_stdio(0);
int N;
cin >> N;
FR(i, N-1) {
int a, b;
cin >> a >> b;
a--; b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
int K;
cin >> K;
FR(i, K) {
char c;
int x, y, z;
cin >> c;
cin >> x >> y >> z;
x--, y--;
if (x != y) {
if (c == 'm') {
minc[x].insert(z);
minc[y].insert(z);
}
else {
maxc[x].insert(z);
maxc[y].insert(z);
}
}
}
root(0, 0);
queue<int> deq;
unordered_set<int> unvis;
for (int i = 0; i < condense.size(); i++) {
deg[i] = color[i].size();
if (deg[i] == 1) {
deq.push(i);
}
else {
unvis.insert(i);
}
}
while (unvis.size() > 0) {
while (deq.size() > 0) {
int next = deq.front(); deq.pop();
for (int j : color[next]) {
if (!visited[j]) {
visited[j] = true;
cout << j+1 << " " << par[j]+1 << " " << rev[next] << '\n';
for (int e : to[j]) {
deg[e]--;
if (deg[e] == 1 && unvis.count(e)) {
deq.push(e);
unvis.erase(e);
}
}
break;
}
}
}
if (unvis.size() > 0) {
int j = *unvis.begin();
unvis.erase(j);
deq.push(j);
}
}
for (int i = 1; i < N; i++) {
if (!visited[i]) {
if (to[i].size() > 0) {
cout << par[i]+1 << " " << i+1 << " " << rev[to[i][0]] << '\n';
}
else {
cout << par[i]+1 << " " << i+1 << " " << 1 << '\n';
}
}
}
return 0;
}
Compilation message
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:114:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::unordered_map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for (int i = 0; i < condense.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
11884 KB |
Output is correct |
| 2 |
Correct |
8 ms |
11884 KB |
Output is correct |
| 3 |
Correct |
8 ms |
11884 KB |
Output is correct |
| 4 |
Correct |
10 ms |
11884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
334 ms |
56336 KB |
Output is correct |
| 2 |
Correct |
249 ms |
32400 KB |
Output is correct |
| 3 |
Runtime error |
884 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
20332 KB |
Output is correct |
| 2 |
Correct |
131 ms |
20332 KB |
Output is correct |
| 3 |
Correct |
120 ms |
23148 KB |
Output is correct |
| 4 |
Correct |
121 ms |
24940 KB |
Output is correct |
| 5 |
Correct |
143 ms |
21544 KB |
Output is correct |
| 6 |
Correct |
147 ms |
22252 KB |
Output is correct |
| 7 |
Correct |
142 ms |
20972 KB |
Output is correct |
| 8 |
Correct |
141 ms |
20844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
11884 KB |
Output is correct |
| 2 |
Correct |
8 ms |
11884 KB |
Output is correct |
| 3 |
Correct |
8 ms |
11884 KB |
Output is correct |
| 4 |
Correct |
10 ms |
11884 KB |
Output is correct |
| 5 |
Correct |
334 ms |
56336 KB |
Output is correct |
| 6 |
Correct |
249 ms |
32400 KB |
Output is correct |
| 7 |
Runtime error |
884 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 8 |
Halted |
0 ms |
0 KB |
- |
