#include <bits/stdc++.h>
using namespace std;
class Edge{
public:
int to, cap, rev;
Edge(int a, int b, int c){
to = a;
cap = b;
rev = c;
}
};
class Flow{
public:
int n = 140010;
vector<Edge> adj[140010];
int dist[140010];
int nxt[140010];
bool v[140010];
Flow(){
}
void add(int i, int j){
adj[i].push_back(Edge(j,1,adj[j].size()));
adj[j].push_back(Edge(i,0,adj[i].size()-1));
}
int dfs(int now, int f){
if(now==1){
return f;
}
int did = 0;
for(; nxt[now]<adj[now].size() && f>0; ){
int i = nxt[now];
int to = adj[now][i].to;
if(adj[now][i].cap>0 && dist[to] == dist[now]+1){
int ret = dfs(to,min(f,adj[now][i].cap));
if(ret>0){
adj[now][i].cap -= ret;
adj[to][adj[now][i].rev].cap += ret;
did += ret;
f -= ret;
}
}
if(f>0){
nxt[now]++;
}
else{
break;
}
}
return did;
}
int bfs(){
for(int i = 0; i<n; i++){
dist[i] = -1;
}
vector<int> li;
dist[0] = 0;
li.push_back(0);
v[0] = false;
nxt[0] = 0;
for(int i = 0; i<li.size(); i++){
int now = li[i];
for(int j = 0; j<adj[now].size(); j++){
int to = adj[now][j].to;
if(dist[to]==-1 && adj[now][j].cap>0){
dist[to] = dist[now]+1;
li.push_back(to);
v[to] = false;
nxt[to] = 0;
if(to==1){
return 1;
}
}
}
}
return 0;
}
int flow(){
int ans = 0;
while(bfs()>0){
//do nothing
ans += dfs(0,n);
}
return ans;
}
};
int maxi[70000];
int mini[70000];
int lc[18][70000];
vector<int> adj[70000];
set<int> maxs[70000];
set<int> mins[70000];
vector<int> remmax[70000];
vector<int> remmin[70000];
int h[70000];
int dfs1(int now, int from, int x){
lc[0][now] = from;
h[now] = x;
for(int i = 0; i<adj[now].size(); i++){
int to = adj[now][i];
if(to==from){
continue;
}
dfs1(to,now,x+1);
}
}
int mgmin(int a, int b){
if(mins[a].size()>mins[b].size()){
swap(a,b);
}
for(auto it = mins[a].begin(); it!=mins[a].end(); it++){
mins[b].insert(*it);
}
mins[a].clear();
return b;
}
int mgmax(int a, int b){
if(maxs[a].size()>maxs[b].size()){
swap(a,b);
}
for(auto it = maxs[a].begin(); it!=maxs[a].end(); it++){
maxs[b].insert(*it);
}
maxs[a].clear();
return b;
}
int lca(int a, int b){
if(a==b){
return a;
}
if(h[a] < h[b]){
swap(a,b);
}
for(int i = 17; i>=0; i--){
if(lc[i][a]!=-1 && h[lc[i][a]]>=h[b]){
a = lc[i][a];
}
}
if(a==b){
return a;
}
for(int i = 17; i>=0; i--){
int toa = lc[i][a];
int tob = lc[i][b];
if(toa!=tob){
a = toa;
b = tob;
}
}
return lc[0][a];
}
pair<int, int> go(int now, int from){
//returns minid, maxid
pair<int, int> ret = make_pair(now,now);
for(int i = 0; i<adj[now].size(); i++){
int to = adj[now][i];
if(to==from){
continue;
}
pair<int, int> got = go(to,now);
ret.first = mgmin(ret.first,got.first);
ret.second = mgmax(ret.second,got.second);
}
for(int i = 0; i<remmax[now].size(); i++){
maxs[ret.second].erase(maxs[ret.second].find(remmax[now][i]));
}
for(int i = 0; i<remmin[now].size(); i++){
mins[ret.first].erase(mins[ret.first].find(remmin[now][i]));
}
if(maxs[ret.second].size()>0){
maxi[now] = *maxs[ret.second].begin();
}
else{
maxi[now] = -1;
}
if(mins[ret.first].size()>0){
mini[now] = *mins[ret.first].rbegin();
}
else{
mini[now] = -1;
}
return ret;
}
int main(){
// cout << "MAIN " << endl;
// Flow f = Flow();
// cout << "X " << endl;
// f.add(0,1);
// f.add(0,4);
// f.add(0,69);
// f.add(69,42);
// f.add(42,13);
// f.add(42,1);
// cout << "Y " << endl;
// cout << f.flow() << endl;
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i<n; i++){
int a, b;
cin >> a >> b;
a--;
b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs1(0,-1,0);
for(int i = 1; i<18; i++){
for(int j = 0; j<n; j++){
if(lc[i-1][j]==-1){
lc[i][j] = -1;
}
else{
lc[i][j] = lc[i-1][lc[i-1][j]];
}
}
}
int q;
cin >> q;
for(int i = 0; i<q; i++){
string s;
int a, b, v;
cin >> s >> a >> b >> v;
a--;
b--;
int l = lca(a,b);
if(s=="M"){
//maxi
maxs[a].insert(v);
maxs[b].insert(v);
remmax[l].push_back(v);
}
else{
mins[a].insert(v);
mins[b].insert(v);
remmin[l].push_back(v);
}
}
go(0,-1);
map<int, int> m;
map<int, int> rev;
int point = 2+n;
Flow f = Flow();
for(int i = 1; i<n; i++){
if(mini[i]!=-1 && m.find(mini[i])==m.end()){
rev[point] = mini[i];
f.add(point,1);
m[mini[i]] = point++;
}
if(maxi[i]!=-1 && m.find(maxi[i])==m.end()){
rev[point] = maxi[i];
f.add(point,1);
m[maxi[i]] = point++;
}
}
for(int i = 1; i<n; i++){
f.add(0,2+i);
if(mini[i]!=-1){
f.add(2+i,m[mini[i]]);
}
if(maxi[i]!=-1){
f.add(2+i,m[maxi[i]]);
}
}
f.flow();
for(int i = 1; i<n; i++){
int found = -1;
for(int j = 0; j<f.adj[2+i].size(); j++){
int to = f.adj[2+i][j].to;
if(to!=0 && f.adj[2+i][j].cap==0){
found = rev[to];
}
}
cout << (i+1) << " " << (lc[0][i]+1) << " ";
if(found!=-1){
cout << found << "\n";
}
else if(maxi[i]!=-1){
cout << maxi[i] << "\n";
}
else if(mini[i]!=-1){
cout << mini[i] << "\n";
}
else{
cout << 69 << "\n";
}
}
}
Compilation message
minmaxtree.cpp: In member function 'int Flow::dfs(int, int)':
minmaxtree.cpp:31:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; nxt[now]<adj[now].size() && f>0; ){
~~~~~~~~^~~~~~~~~~~~~~~~
minmaxtree.cpp: In member function 'int Flow::bfs()':
minmaxtree.cpp:61:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<li.size(); i++){
~^~~~~~~~~~
minmaxtree.cpp:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j<adj[now].size(); j++){
~^~~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'int dfs1(int, int, int)':
minmaxtree.cpp:99:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<adj[now].size(); i++){
~^~~~~~~~~~~~~~~~
minmaxtree.cpp:106:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
minmaxtree.cpp: In function 'std::pair<int, int> go(int, int)':
minmaxtree.cpp:155:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<adj[now].size(); i++){
~^~~~~~~~~~~~~~~~
minmaxtree.cpp:164:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<remmax[now].size(); i++){
~^~~~~~~~~~~~~~~~~~~
minmaxtree.cpp:167:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<remmin[now].size(); i++){
~^~~~~~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:269:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j<f.adj[2+i].size(); j++){
~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
15736 KB |
Output is correct |
| 2 |
Correct |
19 ms |
15848 KB |
Output is correct |
| 3 |
Correct |
20 ms |
15924 KB |
Output is correct |
| 4 |
Correct |
23 ms |
15924 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
807 ms |
45792 KB |
Output is correct |
| 2 |
Correct |
676 ms |
45792 KB |
Output is correct |
| 3 |
Correct |
638 ms |
45792 KB |
Output is correct |
| 4 |
Correct |
776 ms |
47124 KB |
Output is correct |
| 5 |
Correct |
743 ms |
47124 KB |
Output is correct |
| 6 |
Correct |
771 ms |
47124 KB |
Output is correct |
| 7 |
Correct |
641 ms |
47124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
332 ms |
47124 KB |
Output is correct |
| 2 |
Correct |
392 ms |
47124 KB |
Output is correct |
| 3 |
Correct |
332 ms |
47124 KB |
Output is correct |
| 4 |
Correct |
319 ms |
47124 KB |
Output is correct |
| 5 |
Correct |
419 ms |
47124 KB |
Output is correct |
| 6 |
Correct |
488 ms |
47124 KB |
Output is correct |
| 7 |
Correct |
440 ms |
47124 KB |
Output is correct |
| 8 |
Correct |
388 ms |
47124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
15736 KB |
Output is correct |
| 2 |
Correct |
19 ms |
15848 KB |
Output is correct |
| 3 |
Correct |
20 ms |
15924 KB |
Output is correct |
| 4 |
Correct |
23 ms |
15924 KB |
Output is correct |
| 5 |
Correct |
807 ms |
45792 KB |
Output is correct |
| 6 |
Correct |
676 ms |
45792 KB |
Output is correct |
| 7 |
Correct |
638 ms |
45792 KB |
Output is correct |
| 8 |
Correct |
776 ms |
47124 KB |
Output is correct |
| 9 |
Correct |
743 ms |
47124 KB |
Output is correct |
| 10 |
Correct |
771 ms |
47124 KB |
Output is correct |
| 11 |
Correct |
641 ms |
47124 KB |
Output is correct |
| 12 |
Correct |
332 ms |
47124 KB |
Output is correct |
| 13 |
Correct |
392 ms |
47124 KB |
Output is correct |
| 14 |
Correct |
332 ms |
47124 KB |
Output is correct |
| 15 |
Correct |
319 ms |
47124 KB |
Output is correct |
| 16 |
Correct |
419 ms |
47124 KB |
Output is correct |
| 17 |
Correct |
488 ms |
47124 KB |
Output is correct |
| 18 |
Correct |
440 ms |
47124 KB |
Output is correct |
| 19 |
Correct |
388 ms |
47124 KB |
Output is correct |
| 20 |
Correct |
730 ms |
47124 KB |
Output is correct |
| 21 |
Correct |
759 ms |
47124 KB |
Output is correct |
| 22 |
Correct |
819 ms |
47124 KB |
Output is correct |
| 23 |
Correct |
823 ms |
47124 KB |
Output is correct |
| 24 |
Correct |
900 ms |
51200 KB |
Output is correct |
| 25 |
Correct |
895 ms |
52604 KB |
Output is correct |
| 26 |
Correct |
936 ms |
52604 KB |
Output is correct |
| 27 |
Execution timed out |
1080 ms |
52604 KB |
Time limit exceeded |
| 28 |
Halted |
0 ms |
0 KB |
- |
