#include <bits/stdc++.h>
using namespace std;
class Edge{
public:
int to, rev;
bool cap;
Edge(int a, bool 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];
int li[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));
}
bool dfs(int now){
if(now==1){
return true;
}
for(; nxt[now]<adj[now].size(); nxt[now]++){
int i = nxt[now];
int to = adj[now][i].to;
if(adj[now][i].cap && dist[to] == dist[now]+1 && dfs(to)){
adj[now][i].cap = false;
adj[to][adj[now][i].rev].cap = true;
return true;
}
}
return false;
}
int bfs(){
for(int i = 0; i<n; i++){
dist[i] = -1;
}
dist[0] = 0;
int point = 1;
v[0] = false;
nxt[0] = 0;
for(int i = 0; i<point; 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[point++] = to;
nxt[to] = 0;
if(to==1){
return 1;
}
}
}
}
return 0;
}
int flow(){
int ans = 0;
while(bfs()>0){
//do nothing
ans += dfs(0);
}
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];
}
}
if(found!=-1){
printf("%d %d %d\n", i+1, lc[0][i]+1, found);
}
else if(maxi[i]!=-1){
printf("%d %d %d\n", i+1, lc[0][i]+1, maxi[i]);
}
else if(mini[i]!=-1){
printf("%d %d %d\n", i+1, lc[0][i]+1, mini[i]);
}
else{
printf("%d %d %d\n", i+1, lc[0][i]+1, 69);
}
}
}
Compilation message
minmaxtree.cpp: In member function 'bool Flow::dfs(int)':
minmaxtree.cpp:32:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; nxt[now]<adj[now].size(); nxt[now]++){
~~~~~~~~^~~~~~~~~~~~~~~~
minmaxtree.cpp: In member function 'int Flow::bfs()':
minmaxtree.cpp:53: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:88:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<adj[now].size(); i++){
~^~~~~~~~~~~~~~~~
minmaxtree.cpp:95: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:144:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<adj[now].size(); i++){
~^~~~~~~~~~~~~~~~
minmaxtree.cpp:153:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i<remmax[now].size(); i++){
~^~~~~~~~~~~~~~~~~~~
minmaxtree.cpp:156: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:258:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j<f.adj[2+i].size(); j++){
~^~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
15864 KB |
Output is correct |
| 2 |
Correct |
18 ms |
15864 KB |
Output is correct |
| 3 |
Correct |
22 ms |
15900 KB |
Output is correct |
| 4 |
Correct |
19 ms |
15924 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1074 ms |
44076 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1052 ms |
44076 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
15864 KB |
Output is correct |
| 2 |
Correct |
18 ms |
15864 KB |
Output is correct |
| 3 |
Correct |
22 ms |
15900 KB |
Output is correct |
| 4 |
Correct |
19 ms |
15924 KB |
Output is correct |
| 5 |
Execution timed out |
1074 ms |
44076 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
