#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int nmax=70005;
vector<int> v[nmax],ad[nmax];
pair<int,int> st[nmax],dr[nmax];
bool viz[nmax];
int l[nmax],r[nmax];
int T[nmax],rg[nmax],low[nmax];
int rmq[20][2*nmax];
int tt[nmax],mark[nmax],first[nmax],lev[nmax];
int n,m,i,j,L,val,a,b,nr,niv,lg[2*nmax],idx;
char ch;
bool changed=0;
struct restr
{
int value,n1,n2,wh;
};
bool comp(restr unu,restr doi)
{
return unu.value<doi.value;
}
vector<restr> mins,maxs;
int minlev(int A,int B)
{
if(lev[A]<lev[B]) return A;
return B;
}
void build_rmq()
{
for(i=2;i<=nr;i++)
lg[i]=lg[i/2]+1;
for(i=1;(1<<i)<=nr;i++)
for(j=1;j<=nr-(1<<i)+1;j++)
rmq[i][j]=minlev(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
}
void dfs(int x)
{
rmq[0][++nr]=x;first[x]=nr;
for(int i=0;i<v[x].size();i++)
if(!tt[v[x][i]])
{
lev[v[x][i]]=lev[x]+1;
tt[v[x][i]]=x;
dfs(v[x][i]);
rmq[0][++nr]=x;
}
}
int lca(int unu,int doi)
{
unu=first[unu];doi=first[doi];
if(unu>doi) swap(unu,doi);
niv=lg[doi-unu+1];
return minlev(rmq[niv][unu],rmq[niv][doi-(1<<niv)+1]);
}
int finds(int x)
{
while(x!=T[x])
x=T[x];
return x;
}
void unite(int A,int B)
{
if(A==B) return;
if(rg[A]>rg[B]) {T[B]=A;rg[A]+=rg[B];low[A]=minlev(low[A],low[B]);}
else {T[A]=B;rg[B]+=rg[A];low[B]=minlev(low[A],low[B]);}
}
void set_mn(int x,int y)
{
while(x!=-1&&lev[x]>lev[L])
{
if(val>st[x].first)
st[x]={val,idx};
if(!T[x]) T[x]=x;
if(T[tt[x]])
unite(finds(x),finds(tt[x]));
x=tt[low[finds(x)]];
}
while(y!=-1&&lev[y]>lev[L])
{
if(val>st[y].first)
st[y]={val,idx};
if(!T[y]) T[y]=y;
if(T[tt[y]])
unite(finds(y),finds(tt[y]));
y=tt[low[finds(y)]];
}
}
void set_mx(int x,int y)
{
while(x!=-1&&lev[x]>lev[L])
{
if(val<dr[x].first)
dr[x]={val,idx};
if(!T[x]) T[x]=x;
if(T[tt[x]])
unite(finds(x),finds(tt[x]));
x=tt[low[finds(x)]];
}
while(y!=-1&&lev[y]>lev[L])
{
if(val<dr[y].first)
dr[y]={val,idx};
if(!T[y]) T[y]=y;
if(T[tt[y]])
unite(finds(y),finds(tt[y]));
y=tt[low[finds(y)]];
}
}
bool cup(int x)
{
if(viz[x]) return 0;
viz[x]=1;
for(int i=0;i<ad[x].size();i++)
if(!r[ad[x][i]])
{
l[x]=ad[x][i];
r[ad[x][i]]=x;
return 1;
}
for(int i=0;i<ad[x].size();i++)
if(cup(r[ad[x][i]]))
{
l[x]=ad[x][i];
r[ad[x][i]]=x;
return 1;
}
return 0;
}
int main()
{
//freopen("data.in","r",stdin);
ios_base::sync_with_stdio(false);
cin>>n;
for(i=1;i<=n-1;i++)
{
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
tt[1]=-1;
dfs(1);
for(i=1;i<=n;i++)
st[i]={-1,0},dr[i]={(1<<30),0};
build_rmq();
cin>>m;
for(i=1;i<=m;i++)
{
cin>>ch>>a>>b>>val;
if(ch=='m') mins.push_back({val,a,b,i});
else maxs.push_back({val,a,b,i});
}
sort(mins.begin(),mins.end(),comp);
sort(maxs.begin(),maxs.end(),comp);
for(i=1;i<=n;i++)
T[i]=0,low[i]=i,rg[i]=1;
if(mins.size())
for(i=mins.size()-1;i>=0;i--)
{
a=mins[i].n1;b=mins[i].n2;val=mins[i].value;idx=mins[i].wh;
L=lca(a,b);
set_mn(a,b);
}
for(i=1;i<=n;i++)
T[i]=0,low[i]=i,rg[i]=1;
for(i=0;i<maxs.size();i++)
{
a=maxs[i].n1;b=maxs[i].n2;val=maxs[i].value;idx=maxs[i].wh;
L=lca(a,b);
set_mx(a,b);
}
for(i=1;i<=n;i++)
{
if(st[i].second) ad[i].push_back(st[i].second);
if(dr[i].second) ad[i].push_back(dr[i].second);
}
changed=1;
while(changed)
{
changed=0;
for(i=1;i<=n;i++)
viz[i]=0;
for(i=1;i<=n;i++)
if((!l[i])&&cup(i))
changed=1;
}
for(i=2;i<=n;i++)
{
if(!l[i])
{
val=1;
if(st[i].second) val=st[i].first;
if(dr[i].second) val=dr[i].first;
cout<<i<<' '<<tt[i]<<' '<<val<<'\n';
}
else
{
if(l[i]==st[i].second) val=st[i].first;
else val=dr[i].first;
cout<<i<<' '<<tt[i]<<' '<<val<<'\n';
}
}
return 0;
}
Compilation message
minmaxtree.cpp: In function 'void dfs(int)':
minmaxtree.cpp:42:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
minmaxtree.cpp: In function 'bool cup(int)':
minmaxtree.cpp:116:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ad[x].size();i++)
~^~~~~~~~~~~~~
minmaxtree.cpp:123:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ad[x].size();i++)
~^~~~~~~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:169:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<maxs.size();i++)
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3704 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3872 KB |
Output is correct |
| 3 |
Correct |
5 ms |
3872 KB |
Output is correct |
| 4 |
Correct |
5 ms |
3872 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
176 ms |
25444 KB |
Output is correct |
| 2 |
Correct |
157 ms |
25444 KB |
Output is correct |
| 3 |
Execution timed out |
1097 ms |
25444 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
25444 KB |
Output is correct |
| 2 |
Correct |
127 ms |
25444 KB |
Output is correct |
| 3 |
Correct |
129 ms |
25444 KB |
Output is correct |
| 4 |
Correct |
147 ms |
25444 KB |
Output is correct |
| 5 |
Correct |
134 ms |
25444 KB |
Output is correct |
| 6 |
Correct |
128 ms |
25444 KB |
Output is correct |
| 7 |
Correct |
153 ms |
25444 KB |
Output is correct |
| 8 |
Correct |
107 ms |
25444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3704 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3872 KB |
Output is correct |
| 3 |
Correct |
5 ms |
3872 KB |
Output is correct |
| 4 |
Correct |
5 ms |
3872 KB |
Output is correct |
| 5 |
Correct |
176 ms |
25444 KB |
Output is correct |
| 6 |
Correct |
157 ms |
25444 KB |
Output is correct |
| 7 |
Execution timed out |
1097 ms |
25444 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
