// And you curse yourself for things you never done
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
vector<int> v[maxn];
int dsu[maxn], up[maxn];
int h[maxn], pr[maxn];
void restart_dsu(){
memset(dsu, -1, sizeof dsu);
iota(up, up + maxn, 0);
}
int fnd(int u){
return dsu[u] < 0 ? u : dsu[u] = fnd(dsu[u]);
}
void mrg(int a, int b){
if( (a = fnd(a)) == (b = fnd(b)) )
return;
if(dsu[a] > dsu[b])
swap(a, b);
dsu[a]+= dsu[b];
dsu[b] = a;
if(h[ up[b] ] < h[ up[a] ])
up[a] = up[b];
}
void prep(int u, int par = 0){
h[u] = h[par] + 1;
pr[u] = par;
for(int y : v[u])
if(y != par)
prep(y, u);
}
int L[maxn], R[maxn], idL[maxn], idR[maxn];
void MN(int id, int x, int id2){
if(R[id] > x)
R[id] = x, idR[id] = id2;
}
void MX(int id, int x, int id2){
if(L[id] < x)
L[id] = x, idL[id] = id2;
}
int tp[maxn], to[2 * maxn], nxt[2 * maxn], good[2 * maxn], C;
void add(int a, int b, int c){
nxt[C] = tp[a], tp[a] = C, to[C] = b, good[C] = c, C++;
nxt[C] = tp[b], tp[b] = C, to[C] = a, good[C] = c ^ 1, C++;
}
int mark[maxn], choose[maxn];
int cyc(int u, int par = -1){
mark[u] = 1;
for(int id = tp[u]; id != -1; id = nxt[id]){
if(id != par){
if(mark[ to[id] ] == 1)
return u;
int num = cyc(to[id], id ^ 1);
if(num != -1)
return num;
}
}
return -1;
}
void go(int u, int par = -1){
mark[u] = 2;
for(int id = tp[u]; id != -1; id = nxt[id]){
if(id != par){
if(mark[ to[id] ] == 2)
choose[good[id] >> 1] = good[id] & 1;
else if(mark[ to[id] ] != 3)
choose[good[id] >> 1] = good[id] & 1, go(to[id], id ^ 1);
}
}
mark[u] = 3;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
memset(tp, -1, sizeof tp);
memset(idL, -1, sizeof idL);
memset(idR, -1, sizeof idR);
int n;
cin >> n;
for(int i = 0; i < n-1; i++){
int a, b;
cin >> a >> b;
v[a].PB(b);
v[b].PB(a);
}
prep(1);
for(int i = 2; i <= n; i++){
L[i] = -inf, R[i] = inf;
}
int k;
cin >> k;
vector< pair<int, pii> > MXS, MNS;
for(int i = 0; i < k; i++){
char c;
cin >> c;
int a, b, x;
cin >> a >> b >> x;
if(c == 'M')
MNS.PB({x, {a, b}});
else
MXS.PB({x, {a, b}});
}
sort(MNS.begin(), MNS.end());
sort(MXS.begin(), MXS.end());
reverse(MXS.begin(), MXS.end());
int counter = 0;
for(auto x : MNS){
int a = x.S.F, b = x.S.S, X = x.F;
while(fnd(a) != fnd(b)){
a = up[fnd(a)], b = up[fnd(b)];
if(h[a] < h[b])
swap(a, b);
MN(a, X, counter);
mrg(a, pr[a]);
}
counter++;
}
restart_dsu();
for(auto x : MXS){
int a = x.S.F, b = x.S.S, X = x.F;
while(fnd(a) != fnd(b)){
a = up[fnd(a)], b = up[fnd(b)];
if(h[a] < h[b])
swap(a, b);
MX(a, X, counter);
mrg(a, pr[a]);
}
counter++;
}
for(int i = 2; i <= n; i++){
assert(L[i] <= R[i]);
if(idL[i] == -1)
L[i] = R[i];
if(idR[i] == -1)
R[i] = L[i];
if(idL[i] == -1 && idR[i] != -1)
add(idR[i], idR[i], 2 * i + 1);
if(idL[i] != -1 && idR[i] == -1)
add(idL[i], idL[i], 2 * i);
if(L[i] == R[i]){
if(idL[i] != -1 && idR[i] != -1)
add(idL[i], idL[i], 2 * i), add(idR[i], idR[i], 2 * i + 1);
}
else{
assert(idL[i] != -1 && idR[i] != -1);
add(idL[i], idR[i], 2 * i + 1);
}
}
for(int i = 0; i < k; i++){
if(mark[i] == 0){
int u = cyc(i);
assert(u != -1);
go(u);
}
}
for(int i = 2; i <= n; i++){
cout << i << " " << pr[i] << " " << (choose[i] ? R[i] : L[i]) << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
184 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
226 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
201 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
184 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
