#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 7e4;
const int inf = 2e9;
int n, m;
class edge {
public:
int dest, rev_id;
bool full;
edge(int d, bool f, int r) : dest(d), full(f), rev_id(r) {}
};
class dinic {
public:
vector<edge> adj[2*MAXN+1]; // start, end, n-1 edges
int sz, s, t;
dinic() {}
dinic(int sz, int s, int t) : sz(sz), s(s), t(t) {}
int level[MAXN+1];
int ptr[MAXN+1];
void add_edge(int u, int v) {
adj[u].push_back(edge(v, 0, adj[v].size()));
adj[v].push_back(edge(u, 1, adj[u].size()-1));
}
bool bfs() {
queue<int> q;
fill(level, level+sz, -1);
level[s] = 0;
q.push(s);
while (!q.empty() && level[t] == -1) {
int cur = q.front();
q.pop();
for (edge e: adj[cur]) {
if (e.full) continue;
if (level[e.dest] != -1) continue;
level[e.dest] = level[cur]+1;
q.push(e.dest);
}
}
return level[t] != -1;
}
void rev(int cur) {
edge e = adj[cur][ptr[cur]];
adj[cur][ptr[cur]].full = 1;
adj[e.dest][e.rev_id].full = 0;
}
bool get_flow(int cur) {
if (cur == t) return 1;
for (; ptr[cur] != adj[cur].size(); ptr[cur]++) {
edge e = adj[cur][ptr[cur]];
if (level[e.dest] != level[cur]+1 || e.full) continue;
bool is_flow = get_flow(e.dest);
if (is_flow) {
rev(cur);
if (cur != s) {
ptr[cur]++;
return 1;
}
}
}
return 0;
}
void make_match() {
while (bfs()) {
fill(ptr, ptr+sz, 0);
get_flow(s);
}
}
};
vector<pii> edges[MAXN];
vector<pii> max_del[MAXN];
vector<pii> min_del[MAXN];
vector<pii> max_add[MAXN];
vector<pii> min_add[MAXN];
set<pii> *max_vals[MAXN];
set<pii> *min_vals[MAXN];
dinic matcher;
int lca[MAXN][17];
int par_edge_val[MAXN];
int depth[MAXN];
int corr_val[MAXN];
pii edge_list[MAXN];
int req[MAXN];
int get_lca(int x, int y) {
if (depth[x] > depth[y]) return get_lca(y, x);
int def = depth[y]-depth[x];
int pow = 0;
while (def > 0) {
if (def & 1) {
y = lca[y][pow];
}
def >>= 1;
pow++;
}
for (int i = 16; i >= 0; i--) {
if (lca[x][i] != lca[y][i]) {
x = lca[x][i];
y = lca[y][i];
}
}
if (x == y) return x;
return lca[x][0];
}
void dfs(int cur = 0, int p = 0) {
lca[cur][0] = p;
for (pii e: edges[cur]) {
int nxt = e.first;
if (nxt == p) continue;
depth[nxt] = depth[cur]+1;
par_edge_val[nxt] = e.second;
dfs(nxt, cur);
}
}
void make_lca() {
dfs();
for (int i = 1; i < 17; i++) {
for (int j = 0; j < n; j++) lca[j][i] = lca[lca[j][i-1]][i-1];
}
}
set<pii> *merge(set<pii> *a, set<pii> *b) {
if (a->size() > b->size()) return merge(b, a);
for (pii p: (*a)) b->insert(p);
delete a;
return b;
}
void make_dinic(int cur = 0, int p = -1) {
max_vals[cur] = new set<pii>;
min_vals[cur] = new set<pii>;
for (pii e: edges[cur]) {
int nxt = e.first;
if (nxt == p) continue;
make_dinic(nxt, cur);
if (cur > 0) max_vals[cur] = merge(max_vals[cur], max_vals[nxt]);
if (cur > 0) min_vals[cur] = merge(min_vals[cur], min_vals[nxt]);
}
if (cur == 0) return;
matcher.add_edge(n-1, par_edge_val[cur]);
for (pii entry: max_add[cur]) max_vals[cur]->insert(entry);
for (pii entry: max_del[cur]) max_vals[cur]->erase(entry);
for (pii entry: min_add[cur]) min_vals[cur]->insert(entry);
for (pii entry: min_del[cur]) min_vals[cur]->erase(entry);
if (!max_vals[cur]->empty()) matcher.add_edge(par_edge_val[cur], max_vals[cur]->begin()->second+n);
if (!min_vals[cur]->empty()) {
matcher.add_edge(par_edge_val[cur], min_vals[cur]->rbegin()->second+n);
req[par_edge_val[cur]] = min_vals[cur]->rbegin()->first;
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n;
for (int i = 0; i < n-1; i++) {
req[i] = 1;
int x, y; cin >> x >> y;
edge_list[i] = pii(x, y);
x--; y--;
edges[x].push_back(pii(y, i));
edges[y].push_back(pii(x, i));
}
make_lca();
cin >> m;
matcher = dinic(n+m+1, n-1, n+m);
for (int i = 0; i < m; i++) {
char c;
int x, y, v;
cin >> c >> x >> y >> v;
x--; y--;
corr_val[i] = v;
int l = get_lca(x, y);
if (c == 'M') {
max_add[x].push_back(pii(v, i));
max_add[y].push_back(pii(v, i));
max_del[l].push_back(pii(v, i));
}
else {
min_add[x].push_back(pii(v, i));
min_add[y].push_back(pii(v, i));
min_del[l].push_back(pii(v, i));
}
matcher.add_edge(n+i, n+m);
}
make_dinic();
matcher.make_match();
for (int i = 0; i < n-1; i++) {
cout << edge_list[i].first << " " << edge_list[i].second << " ";
bool found = 0;
for (int out = 1; out < matcher.adj[i].size(); out++) {
if (matcher.adj[i][out].full) {
cout << corr_val[matcher.adj[i][out].dest-n] << "\n";
found = 1;
break;
}
}
if (!found) cout << req[i] << "\n";
}
return 0;
}
Compilation message
minmaxtree.cpp: In constructor 'edge::edge(int, bool, int)':
minmaxtree.cpp:14:7: warning: 'edge::full' will be initialized after [-Wreorder]
14 | bool full;
| ^~~~
minmaxtree.cpp:13:12: warning: 'int edge::rev_id' [-Wreorder]
13 | int dest, rev_id;
| ^~~~~~
minmaxtree.cpp:15:2: warning: when initialized here [-Wreorder]
15 | edge(int d, bool f, int r) : dest(d), full(f), rev_id(r) {}
| ^~~~
minmaxtree.cpp: In member function 'bool dinic::get_flow(int)':
minmaxtree.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for (; ptr[cur] != adj[cur].size(); ptr[cur]++) {
| ~~~~~~~~~^~~~~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:198:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
198 | for (int out = 1; out < matcher.adj[i].size(); out++) {
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
16212 KB |
Output is correct |
| 2 |
Correct |
9 ms |
16212 KB |
Output is correct |
| 3 |
Correct |
9 ms |
16212 KB |
Output is correct |
| 4 |
Correct |
9 ms |
16212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1096 ms |
45956 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1062 ms |
33332 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
16212 KB |
Output is correct |
| 2 |
Correct |
9 ms |
16212 KB |
Output is correct |
| 3 |
Correct |
9 ms |
16212 KB |
Output is correct |
| 4 |
Correct |
9 ms |
16212 KB |
Output is correct |
| 5 |
Execution timed out |
1096 ms |
45956 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
