#include <iostream>
#include <fstream>
#include <vector>
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 tt[nmax],mark[nmax];
int n,m,i,j,L,val,a,b;
char ch;
bool changed=0;
void dfs(int x)
{
for(int i=0;i<v[x].size();i++)
if(!tt[v[x][i]])
{
tt[v[x][i]]=x;
dfs(v[x][i]);
}
}
int lca(int x,int y)
{
int aux=x;
while(x!=-1)
mark[x]=1,x=tt[x];
while(!mark[y])
y=tt[y];
while(aux!=-1)
mark[aux]=0,aux=tt[aux];
return y;
}
void set_mn(int x,int y)
{
while(x!=L)
{
if(val>st[x].first)
st[x]={val,i};
x=tt[x];
}
while(y!=L)
{
if(val>st[y].first)
st[y]={val,i};
y=tt[y];
}
}
void set_mx(int x,int y)
{
while(x!=L)
{
if(val<dr[x].first)
dr[x]={val,i};
x=tt[x];
}
while(y!=L)
{
if(val<dr[y].first)
dr[y]={val,i};
y=tt[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);
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};
cin>>m;
for(i=1;i<=m;i++)
{
cin>>ch>>a>>b>>val;
L=lca(a,b);
if(ch=='m') set_mn(a,b);
else 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])
{
cout<<i<<' '<<tt[i]<<' '<<"1\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:16:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
minmaxtree.cpp: In function 'void set_mn(int, int)':
minmaxtree.cpp:44:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(val>st[y].first)
^~
minmaxtree.cpp:46:10: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
y=tt[y];
^
minmaxtree.cpp: In function 'bool cup(int)':
minmaxtree.cpp:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ad[x].size();i++)
~^~~~~~~~~~~~~
minmaxtree.cpp:75:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ad[x].size();i++)
~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
3576 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3688 KB |
Output is correct |
| 3 |
Correct |
6 ms |
3892 KB |
Output is correct |
| 4 |
Correct |
6 ms |
3892 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1083 ms |
8884 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
198 ms |
10976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
3576 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3688 KB |
Output is correct |
| 3 |
Correct |
6 ms |
3892 KB |
Output is correct |
| 4 |
Correct |
6 ms |
3892 KB |
Output is correct |
| 5 |
Execution timed out |
1083 ms |
8884 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
