#include "rail.h" #include <bits/stdc++.h> #define pb push_back #define fst first #define snd second #define fore(i,a,b) for(int i=a,pao=b;i<pao;++i) #define SZ(x) ((int)x.size()) #define ALL(x) x.begin(),x.end() #define mset(a,v) memset((a),(v),sizeof(a)) #define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) using namespace std; typedef long long ll; #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template <typename T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const int MAXN=5005,INF=1e9; int d[MAXN][MAXN]; void findLocation(int N, int first, int location[], int stype[]) { stype[0]=1;location[0]=first; fore(i,0,N)fore(j,i+1,N){ d[i][j]=d[j][i]=getDistance(i,j); } vector<int>dist(N,INF); vector<bool>vis(N,0); using T=tuple<int,int,int>; priority_queue<T,vector<T>,greater<T>>pq; dist[0]=0; vis[0]=1; fore(i,1,N){ if(dist[i]>d[0][i]){ dist[i]=d[0][i]; pq.push({d[0][i],0,i}); } } while(SZ(pq)){ auto[sum,from,to]=pq.top();pq.pop(); if(vis[to])continue; vis[to]=1; stype[to]=(stype[from]==1?2:1); location[to]=location[from]+(stype[from]==1?d[from][to]:-d[from][to]); // como determino el bloque? fore(i,1,N){ if(vis[i])continue; if(dist[i]>d[to][i]){ dist[i]=d[to][i]; pq.push({dist[i],to,i}); } } } //~ fore(i,0,N)cout<<stype[i]<<" "; //~ cout<<endl; //~ fore(i,0,N)cout<<location[i]<<" "; return; } // ( ) )