#include<bits/stdc++.h>
using namespace std;
int n,k;
vector<int> con_cuplaj[140005];
int tole[140005],tori[140005];
void add_edge(int xle, int xri)
{
con_cuplaj[xle].push_back(xri);
con_cuplaj[xri].push_back(xle);
}
int visited[140005],pas;
bool cupleaza(int nod)
{
if(visited[nod]==pas)
return 0;
visited[nod]=pas;
for(auto x:con_cuplaj[nod])
{
if(tole[x]==0)
{
tori[nod]=x;
tole[x]=nod;
return 1;
}
}
for(auto x:con_cuplaj[nod])
{
if(cupleaza(tole[x]))
{
tori[nod]=x;
tole[x]=nod;
return 1;
}
}
return 0;
}
void cuplaj()
{
while(1)
{
pas++;
bool bl=0;
for(int i=1;i<=k;i++)
if(tori[i]==0)
bl |= cupleaza(i);
if(!bl)
break;
}
}
vector<int> con[70005];
pair<int,int> lim[70005];
pair<int,int> care[70005];
int val[70005];
vector<pair<pair<int,int>,int>> baga[70005];
vector<pair<pair<int,int>,int>> scoate[70005];
int parent[70005];
int depth[70005];
int head[70005];
int pos[70005],curpos;
int siz[70005];
int ord[70005];
void dfs_init(int nod)
{
siz[nod]=1;
for(auto adj:con[nod])
{
if(adj!=parent[nod])
{
parent[adj] = nod;
depth[adj] = depth[nod]+1;
dfs_init(adj);
siz[nod] += siz[adj];
}
}
}
void decomp(int nod, int chead)
{
pos[nod]=++curpos;
ord[pos[nod]]=nod;
head[nod]=chead;
int maxc=-1,heavy=-1;
for(auto adj:con[nod])
{
if(adj!=parent[nod] && siz[adj]>maxc)
{
maxc=siz[adj];
heavy=adj;
}
}
if(heavy!=-1)
decomp(heavy,chead);
for(auto adj:con[nod])
if(adj!=parent[nod] && adj!=heavy)
decomp(adj,adj);
}
void add_val(int le, int ri, pair<pair<int,int>,int> newv)
{
if(le>ri)
return;
baga[le].push_back(newv);
scoate[ri+1].push_back(newv);
}
void add_hld(int a, int b, pair<pair<int,int>,int> newv)
{
for(;head[a]!=head[b];b=parent[head[b]])
{
if(depth[head[a]]>depth[head[b]])
swap(a,b);
add_val(pos[head[b]],pos[b],newv);
}
if(pos[a]>pos[b])
swap(a,b);
add_val(pos[a]+1,pos[b],newv);
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n;
int a,b,c;
for(int i=1;i<n;i++)
{
cin>>a>>b;
con[a].push_back(b);
con[b].push_back(a);
}
dfs_init(1);
decomp(1,1);
cin>>k;
char ch;
for(int i=1;i<=k;i++)
{
cin>>ch>>a>>b>>c;
val[i]=c;
if(ch=='M')
{
add_hld(a,b,{{c,i},1});
}
else
{
add_hld(a,b,{{c,i},0});
}
}
set<pair<int,int>> s[2];
for(int i=1;i<=n;i++)
{
for(auto x:baga[i]) s[x.second].insert({x.first});
for(auto x:scoate[i]) s[x.second].erase({x.first});
if(s[0].empty())
{
lim[ord[i]].first = -1;
care[ord[i]].first = -1;
}
else
{
lim[ord[i]].first = (*prev(s[0].end())).first;
care[ord[i]].first = (*prev(s[0].end())).second;
}
if(s[1].empty())
{
lim[ord[i]].second = -1;
care[ord[i]].second = -1;
}
else
{
lim[ord[i]].second = (*s[1].begin()).first;
care[ord[i]].second = (*s[1].begin()).second;
}
}
for(int i=1;i<=n;i++)
{
//cout<<i<<" "<<lim[i].first<<" "<<care[i].first<<" limita inferioara\n";
//cout<<i<<" "<<lim[i].second<<" "<<care[i].second<<" limita superioara\n\n";
if(care[i].first != -1) add_edge(care[i].first, k+i);
if(care[i].second != -1) add_edge(care[i].second, k+i);
}
cuplaj();
int cate=0;
for(int i=1;i<=k;i++)
{
if(tori[i]==0)
{
while(1);
}
}
for(int i=2;i<=n;i++)
{
cout<<i<<" "<<parent[i]<<" ";
if(tole[k+i]==0)
{
if(lim[i].first!=-1) cout<<lim[i].first<<"\n";
else if(lim[i].second!=-1) cout<<lim[i].second<<"\n";
else cout<<1<<"\n";
}
else
{
cout<<val[tole[k+i]]<<"\n";
}
}
return 0;
}
Compilation message
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:180:9: warning: unused variable 'cate' [-Wunused-variable]
180 | int cate=0;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
13148 KB |
Output is correct |
| 2 |
Execution timed out |
1084 ms |
13128 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1040 ms |
26692 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1062 ms |
20572 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
13148 KB |
Output is correct |
| 2 |
Execution timed out |
1084 ms |
13128 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
