#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define ii pair<int, int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define F0R(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define inf 1000000010
#define maxn 70000
vector<int> adj[maxn];
int pa[maxn][18];
int depth[maxn];
int m[maxn], M[maxn];
void dfs(int u, int p, int d) {
pa[u][0] = p;
depth[u] = d;
for (int v : adj[u]) if (v != p) dfs(v, u, d+1);
}
int lca(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
for (int i = 17; ~i; i--) {
if (depth[pa[a][i]] >= depth[b]) a = pa[a][i];
}
if (a == b) return a;
for (int i = 17; ~i; i--) {
if (pa[a][i] != pa[b][i]) {
a = pa[a][i];
b = pa[b][i];
}
}
return pa[a][0];
}
bool vis[maxn];
map<int, int> match;
vector<int> flowAdj[maxn];
int aug(int x) {
if (vis[x]) return 0;
vis[x] = true;
for (int y : flowAdj[x]) {
if (y == inf) continue;
if (match[y] == -1 || aug(match[y])) {
match[y] = x;
return 1;
}
}
return 0;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n; cin >> n;
F0R(i, n-1) {
int x, y; cin >> x >> y; --x; --y;
adj[x].pb(y); adj[y].pb(x);
}
dfs(0, 0, 0);
FOR(i, 1, 18) {
F0R(j, n) {
pa[j][i] = pa[pa[j][i-1]][i-1];
}
}
int k; cin >> k;
vector<pair<int, ii>> minimum, maximum;
F0R(i, k) {
char c; cin >> c;
int a, b, w; cin >> a >> b >> w; --a; --b;
int l = lca(a, b);
if (c == 'M') {
maximum.pb(mp(w, mp(a, l)));
maximum.pb(mp(w, mp(b, l)));
} else {
minimum.pb(mp(w, mp(a, l)));
minimum.pb(mp(w, mp(b, l)));
}
}
sort(all(maximum));
sort(all(minimum));
reverse(all(minimum));
vector<int> nxt(n);
F0R(i, n) nxt[i] = pa[i][0];
F0R(i, n) M[i] = inf;
for (auto event : maximum) {
int v = event.f, a = event.s.f, b = event.s.s;
vector<int> toUpd;
while (depth[a] > depth[b]) {
M[a] = min(M[a], v);
toUpd.pb(a);
a = nxt[a];
}
for (auto x : toUpd) {
nxt[x] = a;
}
}
F0R(i, n) nxt[i] = pa[i][0];
for (auto event : minimum) {
int v = event.f, a = event.s.f, b = event.s.s;
vector<int> toUpd;
while (depth[a] > depth[b]) {
M[a] = max(M[a], v);
toUpd.pb(a);
a = nxt[a];
}
for (auto x : toUpd) {
nxt[x] = a;
}
}
set<int> freeV;
FOR(i, 1, n) {
// cout << i << "-->" << pa[i][0] << ": " << m[i] << " "<< M[i] << endl;
flowAdj[i].pb(m[i]);
flowAdj[i].pb(M[i]);
match[m[i]] = match[M[i]] = -1;
freeV.insert(i);
}
int flow = 0;
FOR(i, 1, n) {
vector<int> candidates;
for (auto r : flowAdj[i]) {
if (r == inf) continue;
if (match[r] == -1) candidates.pb(r);
}
if (sz(candidates)>0) {
flow++;
freeV.erase(i);
int idx = rand()%sz(candidates);
match[candidates[idx]] = i;
}
}
for (auto x : freeV) {
fill(vis, vis+n, false);
flow += aug(x);
}
assert(flow == sz(match)-1);
fill(vis, vis+n, false);
for (auto x : match) {
if (x.f == inf) continue;
assert(x.s != -1);
cout << x.s+1 << " " << pa[x.s][0]+1 << " " << x.f << endl;
vis[x.s] = true;
}
FOR(i, 1, n) {
if (!vis[i]) {
cout << i+1 << " " << pa[i][0]+1 << " " << m[i] << endl;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
480 ms |
25520 KB |
Output is correct |
| 2 |
Correct |
432 ms |
25524 KB |
Output is correct |
| 3 |
Correct |
872 ms |
25828 KB |
Output is correct |
| 4 |
Runtime error |
299 ms |
51676 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1081 ms |
18200 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
