#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const int maxn = 70100;
void bad() {
assert(42);
}
int n, k, m, p[maxn];
vector<int> g[maxn];
vector<int> add[maxn];
array<int, 2> range[maxn];
set<int> L[maxn], H[maxn];
void dfs(int v) {
range[v] = {-(1<<30), 1<<30};
auto add_mx = [&](int i) {
range[v][1] = min(range[v][1], i);
if(!H[v].insert(i).second) H[v].erase(i);
};
auto add_mn = [&](int i) {
range[v][0] = max(range[v][0], i);
if(!L[v].insert(i).second) L[v].erase(i);
};
for(auto &i : g[v]) {
p[i] = v;
g[i].erase(find(all(g[i]), v));
dfs(i);
if(L[i].size()+H[i].size() > L[v].size()+H[v].size())
swap(L[i], L[v]), swap(H[i], H[v]);
}
if(L[v].size()) range[v][0] = *L[v].rbegin();
if(H[v].size()) range[v][1] = *H[v].begin();
for(auto &i : g[v]) {
for(auto &x : L[i])
add_mn(x);
for(auto &x : H[i])
add_mx(x);
}
for(auto i : add[v]) {
if(i < 0) add_mx(-i);
else add_mn(i);
}
//for(auto i : L[v]) cout << i << " ";cout << " | " << v << endl;
}
vector<int> vals, dead, ans, deg;
vector<array<int, 2>> cg[maxn];
void add_edge(int u, int v, int id) {
cg[u].push_back({v, id});
cg[v].push_back({u, id});
//cout << u << " " << v << " " << id << endl;
}
void add_loop(int u, int id) {
add_edge(u, u, id);
}
set<array<int, 2>> q;
void kill_edge(int u, int v, int id) {
dead[id] = 1;
ans[id] = u;
q.erase({deg[u], u});
if(v^u) {
q.erase({deg[v], v});
q.insert({--deg[v], v});
}
}
void solve() {
m = vals.size();
dead.resize(n+1);
ans.resize(n+1, -1);
deg.resize(m);
for(int i = 0; i < m; i++) q.insert({deg[i] = cg[i].size(), i});
while(!q.empty()) {
auto v = q.begin()->at(1);
//cout << "sat " << v << endl;
if(deg[v] == 0) bad();
for(auto [dest, id] : cg[v]) if(!dead[id]) {
kill_edge(v, dest, id);
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
//multitest([&](){});
cin >> n;
for(int f, t, i = 1; i < n; i++) {
cin >> f >> t;
g[f].push_back(t);
g[t].push_back(f);
}
int u, v, x;
char c;
cin >> k;
for(int q = 0; q < k; q++) {
cin >> c >> u >> v >> x;
vals.push_back(x);
if(c == 'M') x *= -1;
add[u].push_back(x);
add[v].push_back(x);
}
dfs(1);
sort(all(vals));
vals.erase(unique(all(vals)), vals.end());
for(int i = 2; i <= n; i++) {
int l = range[i][0], r = range[i][1];
if(l > r) bad();
//cout << i << " " << l << " " << r << endl;
if(l >= 0) l = lower_bound(all(vals), l) - vals.begin();
if(r != 1<<30) r = lower_bound(all(vals), r) - vals.begin();
if(l >= 0 && r != 1<<30) {
add_edge(l, r, i);
} else if(l >= 0 || r != 1<<30) {
add_loop(l >= 0 ? l : r, i);
}
}
solve();
for(int i = 2; i <= n; i++) {
if(ans[i] == -1) ans[i] = max(0, range[i][0]);
cout << i << " " << p[i] << " " << vals[ans[i]] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1090 ms |
12032 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1096 ms |
29668 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1083 ms |
21344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1090 ms |
12032 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
