#include "bits/stdc++.h"
using namespace std;
vector <int> g[70010];
int mn[70010];
int mx[70010];
int par[70010];
int dep[70010];
int sub[70010];
int l[70010];
int r[70010];
int al[70010];
int ar[70010];
bool good[70010];
bool vis[70010];
vector <int> aux[70010];
int ans[70010];
vector <int> mnv[70010], mxv[70010];
void dfs(int x, int p) {
sub[x] = 1;
par[x] = p;
for(int e : g[x]) {
int y = l[e] ^ r[e] ^ x;
if(e != p) {
dep[y] = 1 + dep[x];
dfs(y, e);
sub[x] += sub[y];
}
}
}
void putMin(int x, int y, int val) {
mnv[x].push_back(val);
mnv[y].push_back(val);
}
void putMax(int x, int y, int val) {
mxv[x].push_back(val);
mxv[y].push_back(val);
}
void solver(int x, int p, set <int> &mns, set <int> &mxs) {
for(auto i : mnv[x]) mns.insert(i);
for(auto i : mxv[x]) mxs.insert(i);
for(auto e : g[x]) {
int y = l[e] ^ r[e] ^ x;
if(e == p) continue;
set <int> p, q;
solver(y, e, p, q);
if(p.size() > mns.size()) mns.swap(p);
if(q.size() > mxs.size()) mxs.swap(q);
for(auto i : p) {
if(mns.find(i) == mns.end()) {
mns.insert(i);
} else mns.erase(i);
}
for(auto i : q) {
if(mxs.find(i) == mxs.end()) {
mxs.insert(i);
} else mxs.erase(i);
}
}
if(mns.size() > 0) {
mn[p] = *mns.begin();
}
if(mxs.size() > 0) {
mx[p] = *mxs.rbegin();
}
}
void normal_assign(int x) {
vis[x] = true;
for(int e : aux[x]) {
int y = al[e] ^ ar[e] ^ x;
if(!vis[y] && !good[y]) {
ans[e] = y;
normal_assign(y);
}
}
}
int anc [70010];
int rev [70010];
int col [70010];
bool found;
void cycle(int x, int p) {
col[x] = 1;
anc[x] = p;
for(int e : aux[x]) {
int y = al[e] ^ ar[e] ^ x;
if(col[y] == 0) {
cycle(y, e);
} else if (e != p && col[y] == 1 && !found) {
int cur = x;
while(cur != y) {
int pe = anc[cur];
ans[pe] = cur;
good[cur] = true;
cur ^= al[pe] ^ ar[pe];
}
good[y] = true;
ans[e] = y;
found = true;
}
}
col[x] = -1;
}
int main () {
int n;
scanf("%d", &n);
memset(ans, -1, sizeof ans);
for(int i = 0; i <= n; i++) {
mn[i] = INT_MAX;
mx[i] = INT_MIN;
}
for(int i = 1; i < n; i++) {
scanf("%d %d", &l[i], &r[i]);
g[l[i]].push_back(i);
g[r[i]].push_back(i);
}
dfs(1, 0);
map <int, int> t;
int qr;
scanf("%d", &qr);
for(int i = 1; i <= qr; i++) {
char c;
int x, y, val;
scanf(" %c %d %d %d", &c, &x, &y, &val);
if(c == 'M') {
putMin(x, y, val);
} else {
putMax(x, y, val);
}
t[val] = i;
rev[i] = val;
}
set <int> p, q;
solver(1, 0, p, q);
for(int i = 1; i < n; i++) {
if(mx[i] == INT_MIN && mn[i] == INT_MAX) continue;
if(mx[i] == INT_MIN) {
good[t[mn[i]]] = true;
ans[i] = t[mn[i]];
} else if (mn[i] == INT_MAX) {
good[t[mx[i]]] = true;
ans[i] = t[mx[i]];
} else {
al[i] = t[mx[i]];
ar[i] = t[mn[i]];
aux[al[i]].push_back(i);
aux[ar[i]].push_back(i);
}
}
for(int i = 1; i <= qr; i++) {
if(col[i] == 0) {
found = false;
cycle(i, 0);
}
}
for(int i = 1; i <= qr; i++) {
if(good[i] && !vis[i]) {
normal_assign(i);
}
}
set <int> ss;
for(int i = 1; i < n; i++) {
int val;
if(ans[i] == -1) val = 0;
else val = rev[ans[i]];
printf("%d %d %d\n", l[i], r[i], val);
if(val >= 0) {
ss.insert(val);
}
}
}
Compilation message
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:116:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
minmaxtree.cpp:123:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &l[i], &r[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
minmaxtree.cpp:131:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &qr);
~~~~~^~~~~~~~~~~
minmaxtree.cpp:135:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c %d %d %d", &c, &x, &y, &val);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7296 KB |
Output is correct |
| 2 |
Correct |
8 ms |
7296 KB |
Output is correct |
| 3 |
Correct |
11 ms |
7268 KB |
Output is correct |
| 4 |
Correct |
8 ms |
7168 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
344 ms |
31288 KB |
Output is correct |
| 2 |
Correct |
354 ms |
22392 KB |
Output is correct |
| 3 |
Correct |
350 ms |
29264 KB |
Output is correct |
| 4 |
Correct |
422 ms |
34924 KB |
Output is correct |
| 5 |
Correct |
312 ms |
25848 KB |
Output is correct |
| 6 |
Correct |
336 ms |
23800 KB |
Output is correct |
| 7 |
Correct |
348 ms |
22392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
160 ms |
17272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7296 KB |
Output is correct |
| 2 |
Correct |
8 ms |
7296 KB |
Output is correct |
| 3 |
Correct |
11 ms |
7268 KB |
Output is correct |
| 4 |
Correct |
8 ms |
7168 KB |
Output is correct |
| 5 |
Correct |
344 ms |
31288 KB |
Output is correct |
| 6 |
Correct |
354 ms |
22392 KB |
Output is correct |
| 7 |
Correct |
350 ms |
29264 KB |
Output is correct |
| 8 |
Correct |
422 ms |
34924 KB |
Output is correct |
| 9 |
Correct |
312 ms |
25848 KB |
Output is correct |
| 10 |
Correct |
336 ms |
23800 KB |
Output is correct |
| 11 |
Correct |
348 ms |
22392 KB |
Output is correct |
| 12 |
Incorrect |
160 ms |
17272 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
