# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
548351 | ToroTN | Swapping Cities (APIO20_swap) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#include "swap.h"
#define X first
#define Y second
#define pb push_back
#include <vector>
int n,m,dg[100005],u_i,v_i,w_i,x,y,type=-1,flag=-1;
int node,w,deter=2;
vector<pair<int,int> > g[100005];
vector<pair<int,pair<int,int> > > v;
void init(int N, int M,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
n=N;
m=M;
for(int i=0;i<m;i++)
{
u_i=U[i]+1;
v_i=V[i]+1;
w_i=W[i];
g[u_i].pb({v_i,w_i});
g[v_i].pb({u_i,w_i});
++dg[u_i];
++dg[v_i];
v.push_back({w_i,{u_i,v_i}});
if(u_i!=1)flag=0;
}
sort(v.begin(),v.end());
for(int i=1;i<=n;i++)
{
if(dg[i]>2)
{
type=0;
}
}
if(type==-1)
{
deter=0;
for(int i=1;i<=n;i++)if(dg[i]!=2)deter=-1;
}
}
int getMinimumFuelCapacity(int X, int Y)
{
x=X+1;
y=Y+1;
if(type==-1)
{
if(deter==0)return v[v.size()-1].X;
return -1;
}
if(m==n-1&&flag==-1)
{
if(m<=2)return -1;
if(x==1)
{
if(g[y][0].Y>v[2].X)return g[y][0].Y;
return v[2].Xl
}
if(x==v[0].Y.Y&&y==v[1].Y.Y||x==v[1].Y.Y&&y==v[0].Y.Y)return v[2].X;
return max(g[x][0].Y,g[y][0].Y);
}
}