#include <bits/stdc++.h>
using namespace std;
class Edge
{
public:
int i, j, cap;
Edge *rev;
Edge(int ii, int jj, int capp)
{
i = ii;
j = jj;
cap = capp;
rev = NULL;
}
Edge(){
}
};
class IsapSolver
{
public:
int numNodes, source, sink;
vector<vector<Edge* > > adj;
deque<int> q;
deque<Edge*> path;
vector<int> level;
vector<int> curEdge;
vector<int> count;
IsapSolver(int numNodess)
{
numNodes = numNodess;
source = 0;
sink = 1;
for (int i=0; i<numNodes; i++)
{
vector<Edge*> x;
adj.push_back(x);
}
level.resize(numNodes);
curEdge.resize(numNodes);
count.resize(numNodes+1);
}
void add(int i, int j)
{
int cap = 1;
Edge* fwd = new Edge(i, j, cap);
Edge* rev = new Edge(j, i, 0);
fwd->rev = rev;
rev->rev = fwd;
adj[i].push_back(fwd);
adj[j].push_back(rev);
}
void bfs()
{
for(int i = 0; i<level.size(); i++){
level[i] = -1;
}
level[sink] = 0;
q.clear();
q.push_back(sink);
while (q.size()>0)
{
//poll
int i = q.back();
q.pop_back();
for (Edge* e : adj[i])
{
if (e->rev->cap > 0 && level[e->j] == -1)
{
level[e->j] = level[i] + 1;
q.push_back(e->j);
}
}
}
}
int run()
{
bfs();
for (int i=0; i<numNodes; i++)
count[level[i]]++;
int i = source;
int totalFlow = 0;
while (level[source] < numNodes)
{
Edge *admissibleEdge = NULL;
while (curEdge[i] < adj[i].size())
{
Edge* e = adj[i][curEdge[i]];
if (level[i] == level[e->j] + 1 && e->cap > 0)
{
admissibleEdge = e;
break;
}
curEdge[i]++;
}
if (admissibleEdge == NULL)
{
// Relabel & Retreat
count[level[i]]--;
if (count[level[i]] == 0)
return totalFlow;
level[i] = numNodes;
for (Edge* e : adj[i])
if (e->cap > 0)
level[i] = min(level[i], 1+level[e->j]);
count[level[i]]++;
curEdge[i] = 0;
if (i != source)
{
//pop
Edge* e = path.front();
path.pop_front();
i = e->i;
}
}
else
{
path.push_back(admissibleEdge);
i = admissibleEdge->j;
if (i == sink)
{
int bottleneck = 2147483647;
for (Edge* e : path)
bottleneck = min(bottleneck, e->cap);
totalFlow += bottleneck;
Edge *firstZero = NULL;
for (Edge* e : path)
{
e->cap -= bottleneck;
e->rev->cap += bottleneck;
if(e->cap==0){
firstZero = e;
}
}
path.clear();
i = source;
}
}
}
return totalFlow;
}
};
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;
IsapSolver f = IsapSolver(2 + n + q);
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.run();
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]->j;
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 'void IsapSolver::bfs()':
minmaxtree.cpp:62:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<level.size(); i++){
~^~~~~~~~~~~~~
minmaxtree.cpp: In member function 'int IsapSolver::run()':
minmaxtree.cpp:96:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (curEdge[i] < adj[i].size())
minmaxtree.cpp:138:22: warning: variable 'firstZero' set but not used [-Wunused-but-set-variable]
Edge *firstZero = NULL;
^~~~~~~~~
minmaxtree.cpp: In function 'int dfs1(int, int, int)':
minmaxtree.cpp:173:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<adj[now].size(); i++){
~^~~~~~~~~~~~~~~~
minmaxtree.cpp:180: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:229:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<adj[now].size(); i++){
~^~~~~~~~~~~~~~~~
minmaxtree.cpp:238:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<remmax[now].size(); i++){
~^~~~~~~~~~~~~~~~~~~
minmaxtree.cpp:241: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:343: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 |
Runtime error |
26 ms |
23788 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
801 ms |
113016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
451 ms |
113016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
26 ms |
23788 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
