#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
using namespace std;
const int MAXN = (int)(7e4) + 5;
vector<int> adj[MAXN];
int par[MAXN];
int cpar[MAXN][2];
int tin[MAXN];
int tout[MAXN];
vector<int> color[MAXN];
vector<int> to[MAXN];
bool visited[MAXN];
bool seen[MAXN][2];
bool seenMax[MAXN];
int deg[MAXN];
int store[MAXN][3];
unordered_map<int, int> condense;
int rev[MAXN];
int timer = 0;
void root(int n, int p) {
par[n] = p;
cpar[n][0] = p;
cpar[n][1] = p;
tin[n] = timer++;
for (int e : adj[n]) {
if (e != p) {
root(e, n);
}
}
tout[n] = timer++;
}
int next(int n, int k) {
if (!seen[n][k]) {
return n;
}
return (cpar[n][k] = next(cpar[n][k], k));
}
bool is_ancestor(int a, int b) {
return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}
void apply(int a, int b, int z, int k) {
rev[condense.size()] = z;
condense[z] = condense.size();
z = condense[z];
if (is_ancestor(a, b) || is_ancestor(b, a)) {
if (is_ancestor(a, b)) {
swap(a, b);
}
a = next(a, k);
while (!is_ancestor(a, b)) {
color[z].push_back(a);
to[a].push_back(z);
seen[a][k] = true;
a = next(a, k);
}
return;
}
int u = a;
u = next(u, k);
while (!is_ancestor(u, b)) {
color[z].push_back(u);
to[u].push_back(z);
seen[u][k] = true;
u = next(u, k);
}
b = next(b, k);
while (!is_ancestor(b, a)) {
color[z].push_back(b);
to[b].push_back(z);
seen[b][k] = true;
b = next(b, k);
}
}
int main()
{
// freopen("input.in", "r", stdin);
cin.tie(0);
cin.sync_with_stdio(0);
vector<int> mins;
vector<int> maxs;
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--;
store[i][0] = x;
store[i][1] = y;
store[i][2] = z;
if (x != y) {
if (c == 'm') {
mins.push_back(i);
}
else {
maxs.push_back(i);
}
}
}
sort(mins.begin(), mins.end(), [&] (const int& lhs, const int& rhs) {
return store[lhs][2] > store[rhs][2];
});
sort(maxs.begin(), maxs.end(), [&] (const int& lhs, const int& rhs) {
return store[lhs][2] < store[rhs][2];
});
root(0, 0);
for (int i : mins) {
apply(store[i][0], store[i][1], store[i][2], 0);
}
for (int i : maxs) {
apply(store[i][0], store[i][1], store[i][2], 1);
}
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';
assert (to[j].size() >= 2);
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:128:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::unordered_map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for (int i = 0; i < condense.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
10604 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
146 ms |
40956 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
78 ms |
28012 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
10604 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
