#include <bits/stdc++.h>
using namespace std;
class Edge{
public:
long dest, revInd, cap, flow;
Edge(long a, long b, long c){
dest = a;
revInd = b;
cap = c;
flow = 0;
}
};
class Flow{
public:
vector<vector<Edge> > graph;
vector<vector<Edge> > copy;
Flow(long nodes){
graph.resize(nodes);
}
void add(long s, long t){
long cap = 1;
graph[s].push_back(Edge(t,graph[t].size(),cap));
graph[t].push_back(Edge(s,graph[s].size()-1,0));
}
bool bfs(long src, long dest, long dist[]){
for(long i = 0; i<copy.size(); i++){
dist[i] = -1;
}
dist[src] = 0;
long q[copy.size()];
for(long i = 0; i<copy.size(); i++){
q[i] = 0;
}
long pointer = 0;
q[pointer++] = src;
for(long i = 0; i<pointer; i++){
long now = q[i];
for(long j = 0; j<copy[now].size(); j++){
Edge e = copy[now][j];
if(dist[e.dest]<0 && e.flow<e.cap){
dist[e.dest] = dist[now]+1;
q[pointer++] = e.dest;
}
}
}
return dist[dest] >=0;
}
int dfs(long pointer[], long dist[], long dest, long now, long flow){
if(now==dest){
return flow;
}
for(; pointer[now] < copy[now].size(); pointer[now]++){
Edge e = copy[now][pointer[now]];
if(dist[e.dest]==dist[now]+1 && e.flow<e.cap){
long added = dfs(pointer, dist, dest, e.dest, min(flow,e.cap-e.flow));
if(added>0){
copy[now][pointer[now]].flow += added;
copy[e.dest][e.revInd].flow -= added;
return added;
}
}
}
return 0;
}
void copyGraph(){
copy.resize(graph.size());
for(long i = 0; i<graph.size(); i++){
for(long j = 0; j<graph[i].size(); j++){
Edge e = graph[i][j];
copy[i].push_back(Edge(e.dest,e.revInd,e.cap));
}
}
}
long maxFlow(long src, long dest){
copyGraph();
long flow = 0;
long dist[copy.size()];
for(long i = 0; i<copy.size(); i++){
dist[i] = 0;
}
while(bfs(src, dest, dist)){
long pointer[copy.size()];
for(long i = 0; i<copy.size(); i++){
pointer[i] = 0;
}
while(true){
long added = dfs(pointer, dist, dest, src, 2147483647L);
if(added==0){
break;
}
flow+=added;
}
}
return flow;
}
};
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(point+n);
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.maxFlow(0,1);
for(int i = 1; i<n; i++){
int found = -1;
for(int j = 0; j<f.copy[2+i].size(); j++){
int to = f.copy[2+i][j].dest;
if(to!=0 && f.copy[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 'bool Flow::bfs(long int, long int, long int*)':
minmaxtree.cpp:27:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(long i = 0; i<copy.size(); i++){
~^~~~~~~~~~~~
minmaxtree.cpp:32:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(long i = 0; i<copy.size(); i++){
~^~~~~~~~~~~~
minmaxtree.cpp:39:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(long j = 0; j<copy[now].size(); j++){
~^~~~~~~~~~~~~~~~~
minmaxtree.cpp: In member function 'int Flow::dfs(long int*, long int*, long int, long int, long int)':
minmaxtree.cpp:53:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; pointer[now] < copy[now].size(); pointer[now]++){
~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
minmaxtree.cpp: In member function 'void Flow::copyGraph()':
minmaxtree.cpp:68:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(long i = 0; i<graph.size(); i++){
~^~~~~~~~~~~~~
minmaxtree.cpp:69:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(long j = 0; j<graph[i].size(); j++){
~^~~~~~~~~~~~~~~~
minmaxtree.cpp: In member function 'long int Flow::maxFlow(long int, long int)':
minmaxtree.cpp:79:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(long i = 0; i<copy.size(); i++){
~^~~~~~~~~~~~
minmaxtree.cpp:84:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(long i = 0; i<copy.size(); i++){
~^~~~~~~~~~~~
minmaxtree.cpp: In function 'int dfs1(int, int, int)':
minmaxtree.cpp:110:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<adj[now].size(); i++){
~^~~~~~~~~~~~~~~~
minmaxtree.cpp:117: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:166:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<adj[now].size(); i++){
~^~~~~~~~~~~~~~~~
minmaxtree.cpp:175:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<remmax[now].size(); i++){
~^~~~~~~~~~~~~~~~~~~
minmaxtree.cpp:178: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:280:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j<f.copy[2+i].size(); j++){
~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
11896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
901 ms |
74020 KB |
Output is correct |
| 2 |
Correct |
742 ms |
74020 KB |
Output is correct |
| 3 |
Correct |
931 ms |
74020 KB |
Output is correct |
| 4 |
Correct |
789 ms |
75580 KB |
Output is correct |
| 5 |
Correct |
732 ms |
75580 KB |
Output is correct |
| 6 |
Correct |
736 ms |
75580 KB |
Output is correct |
| 7 |
Correct |
746 ms |
75580 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
531 ms |
75580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
11896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
