#include <bits/stdc++.h>
using namespace std;
int n,m,a,b,c;
vector <vector <int> > InComponents;
vector <vector <int> > adj; //the edge list of the KRT
vector <int> TVector;
int RootID; //ID of the root node of the KRT;
struct Edge{
long long Weight;
int Start;
int End;
};
bool operator< (const Edge &x, const Edge &y){
return x.Weight<y.Weight;
}
Edge Elist[500003];
int Depth[500003];
int Deg[500003];
int CurRep[500003]; //id of the respresentative node on the KRT
int Par[500003]; //Parent of node with id i on the KRT;
int Toggle[500003]; //is the i-th node on the KRT toggled?
int Check[500003];
int Ancestor[500003][20];
int Val[500003];//the value of the i-th node of the KRT
vector <int> KRTID;
int GetRep(int u){
if(CurRep[u]==-1){
return u;
}else{
return CurRep[u]=GetRep(CurRep[u]);
}
}
void DSU(int id, int u, int v, int w){
int CurID=n-1+id;
Deg[u]++;
Deg[v]++;
//u and v belongs to the same component. The component now has a cycle. Immediately toggle the root node of the current
//subtree that includes both u and v on the KRT
//Screw partial, binary tree KRT, opt into full-KRT instead
int RepU=GetRep(u), RepV=GetRep(v);
if(RepU==RepV){
Par[RepU]=CurID;
Val[CurID]=w;
adj[RepU].push_back(CurID);
adj[CurID].push_back(RepU);
//The node isn't toggled just yet. Toggle it immediately as there is a cycle
Toggle[CurID]=1;
}else{
//u and v doesn't belong to the same component. Merge them
int OldComp1=RepU, OldComp2=RepV;
adj[RepU].push_back(CurID);
adj[RepV].push_back(CurID);
adj[CurID].push_back(RepU);
adj[CurID].push_back(RepV);
Par[RepU]=CurID;
Par[RepV]=CurID;
CurRep[RepU]=CurID;
CurRep[RepV]=CurID;
Val[CurID]=w; //if I got WA because I forgot to set the fucking node weight to the nodes on the KRT, I'll shove 3 fingers up my ass.
//if either of the components are toggled already (having a cycle OR a vertex with degree >=3)
//OR the merged component has a vertex with degree >3 (either u or v), toggle immediately
if(Toggle[OldComp1]||Toggle[OldComp2]||Deg[u]>2||Deg[v]>2){
Toggle[CurID]=1;
}
}
//cout<<CurID<<" ";
}
void init(int N, int M, vector <int> U, vector <int> V, vector <int> W){
n=N;
m=M;
for(int i=0;i<n+m+5;i++){
InComponents.push_back(TVector);
adj.push_back(TVector);
}
for(int i=1;i<=m;i++){
Elist[i].Weight=W[i-1];
Elist[i].Start=U[i-1];
Elist[i].End=V[i-1];
}
sort(Elist+1,Elist+m+1);
for(int i=0;i<=m+n+1;i++){
CurRep[i]=-1;
Toggle[i]=0;
}
for(int i=1;i<=m;i++){
DSU(i,Elist[i].Start,Elist[i].End,Elist[i].Weight);
}
//The KRT is now built. BFS from the root node and initialize LCA or something
deque <int> dq;
RootID=n+m-1;
dq.push_back(RootID);
Check[RootID]=1;
int Cur;
while(!dq.empty()){
Cur=dq.front();
//cout<<Cur<<" ";
for(int i=0;i<adj[Cur].size();i++){
if(!Check[adj[Cur][i]]){
dq.push_back(adj[Cur][i]);
Check[adj[Cur][i]]=1;
Depth[adj[Cur][i]]=Depth[Cur]+1;
}
}
dq.pop_front();
}
for(int i=0;i<=19;i++){
for(int k=0;k<n+m;k++){
if(i==0){
Ancestor[k][i]=Par[k];
}else{
Ancestor[k][i]=Ancestor[Ancestor[k][i-1]][i-1];
}
}
}
}
int getMinimumFuelCapacity(int x, int y){
//I thought that we actually need to use binary lifting to find LCA and then jump from the LCA to find the nearest
//toggled node on the KRT
//But apparently small-to-large merging ensures that the depth of the tree is always logN or something, so bruteforcing
//it is
//ok nvm this guy is a fucking moron lmao LogN depth my ass. Wrong analysis, wasted 5 minutes. Fuck me
if(Depth[x]<Depth[y]){
swap(x,y);
}
/*
int JumpLevel=Depth[x]-Depth[y];
for(int i=19;i>=0;i--){
if(JumpLevel >> i & 1){
x=Ancestor[x][i];
}
}
if(x==y){
goto SkipPoint;
}
for(int i=19;i>=0;i--){
if(Ancestor[x][i]!=Ancestor[y][i]){
x=Ancestor[x][i];
y=Ancestor[y][i];
}
}
x=Par[x];
y=Par[y];
SkipPoint:;
if(Toggle[x]){
return Val[x];
}
for(int i=19;i>=0;i--){
if(!Toggle[Ancestor[x][i]]){
x=Ancestor[x][i];
}
}
x=Par[x];
if(Toggle[x]&&x!=-1){
return Val[x];
}
return -1;
*/
while(Depth[x]>Depth[y]){
x=Par[x];
}
if(x==y){
goto SkipPoint;
}
while(x!=y){
x=Par[x];
y=Par[y];
}
SkipPoint:
while(!Toggle[x]&&x!=-1){
x=Par[x];
}
if(x!=-1){
return Val[x];
}else{
return -1;
}
}
/*
int q;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
freopen("swap_12_2.in","r",stdin);
cin>>n>>m;
vector <int> U,V,W;
for(int i=1;i<=m;i++){
cin>>a>>b>>c;
U.push_back(a);
V.push_back(b);
W.push_back(c);
}
init(n,m,U,V,W);
deque <int> dq;
cin>>q;
for(int i=1;i<=q;i++){
cin>>a>>b;
dq.push_back(getMinimumFuelCapacity(a,b));
cout<<dq.back()<<"\n";
}
freopen("swap_12_2.out","r",stdin);
int cur, score=0;
for(int i=1;i<=q;i++){
cin>>cur;
if(cur==dq.front()){
score++;
}else{
cout<<dq.front()<<" "<<cur<<" "<<Val[RootID]<<"\n";
}
dq.pop_front();
}
cout<<score<<" "<<q<<" ";
int maxdepth=0;
for(int i=0;i<=n+m+5;i++){
maxdepth=max(maxdepth,Depth[i]);
}
//cout<<maxdepth;
}
*/
/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
*/
Compilation message
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:97:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int i=0;i<adj[Cur].size();i++){
| ~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2063 ms |
14684 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2063 ms |
14684 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2063 ms |
14684 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2063 ms |
14684 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2063 ms |
14684 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2063 ms |
14684 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
