#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<ii,int>
#define sz(x) (x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 1000000005
#define MOD 1000000007
#define N 140005
#define LOG 20
using namespace std;
struct query {
int from,to,cost;
bool operator<(const query& oth) const {
return cost<oth.cost;
}
};
vector<query> Max,Min;
int n,q,x,y,z,totnode;
int dis[N],match[N],deep[N],ata[N],der[N],par[N];
vector<int> v[N],v2[N];
int bul(int node) {
if(ata[node]==node) return node;
return ata[node]=bul(ata[node]);
}
void dfs(int node) {
if(node) {
for(int i:v2[node]) {
if(dis[node]+1==dis[match[i]]) {
dfs(match[i]);
if(dis[match[i]]!=inf) {
match[node]=i;
match[i]=node;
return ;
}
}
}
dis[node]=inf;
}
}
bool bfs() {
queue<int> q;
for(int i=1;i<=n;i++) {
if(!match[i]) {
dis[i]=0;
q.push(i);
}
else dis[i]=inf;
}
dis[0]=inf;
while(!q.empty()) {
int node=q.front();
q.pop();
if(dis[node]<dis[0]) {
for(int i:v2[node]) {
if(dis[match[i]]==inf) {
dis[match[i]]=dis[node]+1;
q.push(match[i]);
}
}
}
}
return (dis[0]!=inf);
}
void hopcroft_karp() {
totnode=n+sz(Max)+sz(Min);
while(bfs()) {
for(int i=1;i<=totnode;i++) if(!match[i]) dfs(i);
}
}
void make(int node,int from,int to) {
while(1) {
from=bul(from);
to=bul(to);
if(to==from) return ;
if(der[from]<der[to]) swap(from,to);
v2[node].pb(from);
v2[from].pb(node);
ata[from]=par[from];
}
}
void init() {
for(int i=1;i<=n;i++) {
ata[i]=i;
}
}
void dfs(int node,int ata) {
par[node]=ata;
der[node]=der[ata]+1;
for(int i:v[node]) {
if(i==ata) continue ;
dfs(i,node);
}
}
int main() {
// freopen("input.txt","r",stdin);
srand(time(NULL));
scanf("%d",&n);
for(int i=1;i<n;i++) {
scanf("%d %d",&x,&y);
v[x].pb(y);
v[y].pb(x);
}
dfs(1,0);
scanf("%d",&q);
while(q--) {
char c;
scanf(" %c %d %d %d",&c,&x,&y,&z);
if(c=='m') Min.pb({x,y,z});
else Max.pb({x,y,z});
}
sort(all(Min));
reverse(all(Min));
sort(all(Max));
init();
for(int i=0;i<sz(Max);i++) make(i+1+n,Max[i].from,Max[i].to);
init();
for(int i=0;i<sz(Min);i++) make(i+1+sz(Max)+n,Min[i].from,Min[i].to);
hopcroft_karp();
for(int i=2;i<=n;i++) {
int cst;
if(match[i]<=n+sz(Max)) cst=Max[match[i]-n-1].cost;
else cst=Min[match[i]-n-sz(Max)-1].cost;
printf("%d %d %d\n",i,par[i],cst);
}
}
Compilation message
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:218:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<sz(Max);i++) make(i+1+n,Max[i].from,Max[i].to);
^
minmaxtree.cpp:222:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<sz(Min);i++) make(i+1+sz(Max)+n,Min[i].from,Min[i].to);
^
minmaxtree.cpp:230:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(match[i]<=n+sz(Max)) cst=Max[match[i]-n-1].cost;
^
minmaxtree.cpp:186:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
minmaxtree.cpp:190:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&x,&y);
~~~~~^~~~~~~~~~~~~~~
minmaxtree.cpp:199:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
~~~~~^~~~~~~~~
minmaxtree.cpp:205:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c %d %d %d",&c,&x,&y,&z);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
6904 KB |
Output is correct |
| 2 |
Correct |
10 ms |
7056 KB |
Output is correct |
| 3 |
Correct |
9 ms |
7056 KB |
Output is correct |
| 4 |
Correct |
9 ms |
7100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
185 ms |
36064 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 |
Incorrect |
188 ms |
36064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
6904 KB |
Output is correct |
| 2 |
Correct |
10 ms |
7056 KB |
Output is correct |
| 3 |
Correct |
9 ms |
7056 KB |
Output is correct |
| 4 |
Correct |
9 ms |
7100 KB |
Output is correct |
| 5 |
Runtime error |
185 ms |
36064 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
