#include<bits/stdc++.h>
using namespace std;
#define LG 20
struct node{
vector<int> sparseTable;
vector<int> neighbours;
int parent;
int depth;
bool built;
int unionPointer;
int minQueryInd;
int maxQueryInd;
bool isEdgeUsed;
};
vector<node> nodes;
struct query{
int ind,a,b,c;
};
vector<query> minQ,maxQ;
int n,k;
string s;
vector<int> queryValue;
vector<vector<pair<int,int> > > queryEdge;
vector<bool> isQueryActive;
vector<int> activeDegree;
vector<int> toProcess;
void build(int ind);
int lca(int a,int b);
int unionTop(int ind){return nodes[ind].unionPointer==ind?ind:nodes[ind].unionPointer=unionTop(nodes[ind].unionPointer);}
int main(){
ios::sync_with_stdio(false);
cin>>n;
nodes.resize(n,{{},{},0,0,false,0,-1,-1,false});
for(int i = 1,a,b ; i < n ; i ++){
cin>>a>>b;--a;--b;
nodes[a].neighbours.push_back(b);
nodes[b].neighbours.push_back(a);
}
build(0);
cin>>k;
queryValue.resize(k);
for(int i = 0,a,b,c ; i < k ; i ++){
cin>>s>>a>>b>>c;
if(s=="m")
minQ.push_back({i,--a,--b,c});
else
maxQ.push_back({i,--a,--b,c});
queryValue[i]=c;
}
sort(minQ.begin(),minQ.end(),[](const query& a,const query& b){return a.c>b.c;});
sort(maxQ.begin(),maxQ.end(),[](const query& a,const query& b){return a.c<b.c;});
for(int i = 0 ; i < n ; i ++)nodes[i].unionPointer=i;
for(query q:minQ){
int l=lca(q.a,q.b);
while((q.a=unionTop(q.a))!=unionTop(l)){
nodes[q.a].minQueryInd=q.ind;
nodes[q.a].unionPointer=unionTop(nodes[q.a].parent);
}
while((q.b=unionTop(q.b))!=unionTop(l)){
nodes[q.b].minQueryInd=q.ind;
nodes[q.b].unionPointer=unionTop(nodes[q.b].parent);
}
}
for(int i = 0 ; i < n ; i ++)nodes[i].unionPointer=i;
for(query q:maxQ){
int l=lca(q.a,q.b);
while((q.a=unionTop(q.a))!=unionTop(l)){
nodes[q.a].maxQueryInd=q.ind;
nodes[q.a].unionPointer=unionTop(nodes[q.a].parent);
}
while((q.b=unionTop(q.b))!=unionTop(l)){
nodes[q.b].maxQueryInd=q.ind;
nodes[q.b].unionPointer=unionTop(nodes[q.b].parent);
}
}
queryEdge.resize(k);
isQueryActive.resize(k);
activeDegree.resize(k);
for(int i = 1 ; i < n ; i ++){
if(nodes[i].minQueryInd!=-1){if(nodes[i].maxQueryInd!=-1){
queryEdge[nodes[i].minQueryInd].push_back({nodes[i].maxQueryInd,i});
queryEdge[nodes[i].maxQueryInd].push_back({nodes[i].minQueryInd,i});
activeDegree[nodes[i].minQueryInd]++;
activeDegree[nodes[i].maxQueryInd]++;
}else{
if(!isQueryActive[nodes[i].minQueryInd]){
isQueryActive[nodes[i].minQueryInd]=true;
nodes[i].isEdgeUsed=true;
toProcess.push_back(nodes[i].minQueryInd);
cout<<i+1<<" "<<nodes[i].parent+1<<" "<<queryValue[nodes[i].minQueryInd]<<endl;
}
}}else{if(nodes[i].maxQueryInd!=-1){
if(!isQueryActive[nodes[i].maxQueryInd]){
isQueryActive[nodes[i].maxQueryInd]=true;
nodes[i].isEdgeUsed=true;
toProcess.push_back(nodes[i].maxQueryInd);
cout<<i+1<<" "<<nodes[i].parent+1<<" "<<queryValue[nodes[i].maxQueryInd]<<endl;
}
}}
}
for(int i = 0 ; i < k ; i ++){
if(isQueryActive[i]||activeDegree[i]>1)continue;
isQueryActive[i]=true;
nodes[queryEdge[i][0].second].isEdgeUsed=true;
toProcess.push_back(i);
cout<<queryEdge[i][0].second+1<<" "<<nodes[queryEdge[i][0].second].parent+1<<" "<<queryValue[i]<<endl;
}
vector<bool> isQueryProcessed(k);
for(int i=0 ; i<k ; ){
int ind;
if(toProcess.size()){
ind=toProcess.back();toProcess.pop_back();
}else{
if(isQueryProcessed[i]){i++;continue;}
ind=i++;
int nodeInd=-1;
for(pair<int,int> linkedQuery:queryEdge[ind]){
if(nodes[linkedQuery.second].isEdgeUsed)continue;
nodeInd=linkedQuery.second;
break;
}
if(nodeInd==-1){return 0;}
isQueryActive[ind]=true;
nodes[nodeInd].isEdgeUsed=true;
cout<<nodeInd+1<<" "<<nodes[nodeInd].parent+1<<" "<<queryValue[ind]<<endl;
}
isQueryProcessed[ind]=true;
for(pair<int,int> linkedQuery:queryEdge[ind]){
if(isQueryActive[linkedQuery.first])continue;
if(--activeDegree[linkedQuery.first]==1){
int nodeInd=-1;
for(pair<int,int> secondLink:queryEdge[linkedQuery.first]){
if(nodes[secondLink.second].isEdgeUsed)continue;
nodeInd=secondLink.second;
break;
}
if(nodeInd==-1){return 0;}
isQueryActive[linkedQuery.first]=true;
nodes[nodeInd].isEdgeUsed=true;
toProcess.push_back(linkedQuery.first);
cout<<nodeInd+1<<" "<<nodes[nodeInd].parent+1<<" "<<queryValue[linkedQuery.first]<<endl;
}
}
}
for(int i = 1 ; i < n ; i ++){
if(!nodes[i].isEdgeUsed){
if(nodes[i].maxQueryInd==-1&&nodes[i].minQueryInd==-1)
cout<<i+1<<" "<<nodes[i].parent+1<<" "<<0<<endl;
else if(nodes[i].maxQueryInd==-1)
cout<<i+1<<" "<<nodes[i].parent+1<<" "<<queryValue[nodes[i].minQueryInd]<<endl;
else
cout<<i+1<<" "<<nodes[i].parent+1<<" "<<queryValue[nodes[i].maxQueryInd]<<endl;
}
}
}
void build(int ind){
nodes[ind].depth=nodes[ nodes[ind].parent ].depth + 1;
nodes[ind].built=true;
nodes[ind].sparseTable.resize(LG, nodes[ind].parent);
for(int i = 1 ; i < LG ; i ++)
nodes[ind].sparseTable[i]=nodes[ nodes[ind].sparseTable[i-1] ].sparseTable[i-1];
for(int neighbour:nodes[ind].neighbours){
if(nodes[neighbour].built)continue;
nodes[neighbour].parent=ind;
build(neighbour);
}
}
int lca(int a,int b){
if(nodes[a].depth<nodes[b].depth)swap(a,b);
for(int i = LG -1,h ; i >= 0 ; i --)if(nodes[ h=nodes[a].sparseTable[i] ].depth>=nodes[b].depth)a=h;
if(a==b)return a;
for(int i = LG-1,h,g ; i >= 0 ; i --)
if((h=nodes[a].sparseTable[i])!=(g=nodes[b].sparseTable[i])) a=h,b=g;
return nodes[a].parent;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
380 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
397 ms |
21624 KB |
Output is correct |
| 2 |
Correct |
318 ms |
19820 KB |
Output is correct |
| 3 |
Correct |
327 ms |
20080 KB |
Output is correct |
| 4 |
Correct |
342 ms |
21864 KB |
Output is correct |
| 5 |
Correct |
326 ms |
19924 KB |
Output is correct |
| 6 |
Correct |
364 ms |
20352 KB |
Output is correct |
| 7 |
Correct |
309 ms |
20068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
272 ms |
17108 KB |
Output is correct |
| 2 |
Correct |
265 ms |
17524 KB |
Output is correct |
| 3 |
Correct |
296 ms |
18204 KB |
Output is correct |
| 4 |
Correct |
300 ms |
18696 KB |
Output is correct |
| 5 |
Correct |
294 ms |
17596 KB |
Output is correct |
| 6 |
Correct |
305 ms |
17988 KB |
Output is correct |
| 7 |
Correct |
282 ms |
17692 KB |
Output is correct |
| 8 |
Incorrect |
172 ms |
16600 KB |
Unexpected end of file - int32 expected |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
380 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
397 ms |
21624 KB |
Output is correct |
| 6 |
Correct |
318 ms |
19820 KB |
Output is correct |
| 7 |
Correct |
327 ms |
20080 KB |
Output is correct |
| 8 |
Correct |
342 ms |
21864 KB |
Output is correct |
| 9 |
Correct |
326 ms |
19924 KB |
Output is correct |
| 10 |
Correct |
364 ms |
20352 KB |
Output is correct |
| 11 |
Correct |
309 ms |
20068 KB |
Output is correct |
| 12 |
Correct |
272 ms |
17108 KB |
Output is correct |
| 13 |
Correct |
265 ms |
17524 KB |
Output is correct |
| 14 |
Correct |
296 ms |
18204 KB |
Output is correct |
| 15 |
Correct |
300 ms |
18696 KB |
Output is correct |
| 16 |
Correct |
294 ms |
17596 KB |
Output is correct |
| 17 |
Correct |
305 ms |
17988 KB |
Output is correct |
| 18 |
Correct |
282 ms |
17692 KB |
Output is correct |
| 19 |
Incorrect |
172 ms |
16600 KB |
Unexpected end of file - int32 expected |
