#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];
bool v[140010];
vector<int> li;
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){
v[now] = true;
li.push_back(now);
if(now==1){
return 1;
}
for(int i = 0; i<adj[now].size(); i++){
if(adj[now][i].cap>0 && !v[adj[now][i].to]){
int ret = dfs(adj[now][i].to);
if(ret>0){
adj[now][i].cap = 0;
adj[adj[now][i].to][adj[now][i].rev].cap = 1;
return 1;
}
}
}
return 0;
}
int flow(){
for(int i = 0; i<n; i++){
v[i] = false;
}
int ans = 0;
while(true){
//do nothing
if(dfs(0)==0){
break;
}
ans++;
for(int i = 0; i<li.size(); i++){
v[li[i]] = false;
}
li.clear();
}
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 << endl;
}
else if(maxi[i]!=-1){
cout << maxi[i] << endl;
}
else if(mini[i]!=-1){
cout << mini[i] << endl;
}
else{
cout << 69 << endl;
}
}
}
Compilation message
minmaxtree.cpp: In member function 'int Flow::dfs(int)':
minmaxtree.cpp:31:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<adj[now].size(); i++){
~^~~~~~~~~~~~~~~~
minmaxtree.cpp: In member function 'int Flow::flow()':
minmaxtree.cpp:54:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<li.size(); i++){
~^~~~~~~~~~
minmaxtree.cpp: In function 'int dfs1(int, int, int)':
minmaxtree.cpp:74:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<adj[now].size(); i++){
~^~~~~~~~~~~~~~~~
minmaxtree.cpp:81: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:130:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<adj[now].size(); i++){
~^~~~~~~~~~~~~~~~
minmaxtree.cpp:139:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<remmax[now].size(); i++){
~^~~~~~~~~~~~~~~~~~~
minmaxtree.cpp:142: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:244: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 |
18 ms |
15352 KB |
Output is correct |
| 2 |
Correct |
18 ms |
15460 KB |
Output is correct |
| 3 |
Correct |
18 ms |
15460 KB |
Output is correct |
| 4 |
Correct |
18 ms |
15460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1075 ms |
42636 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1060 ms |
42636 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
15352 KB |
Output is correct |
| 2 |
Correct |
18 ms |
15460 KB |
Output is correct |
| 3 |
Correct |
18 ms |
15460 KB |
Output is correct |
| 4 |
Correct |
18 ms |
15460 KB |
Output is correct |
| 5 |
Execution timed out |
1075 ms |
42636 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
