| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 409885 | fadi57 | 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 "swap.h"
#include "grader.cpp"
#include<bits/stdc++.h>
using namespace std;
const int mx=2e5+10;
typedef long long ll;
int inf=1e9+10;
const int mod=1e9+7;
vector<pair<int,int>>adj[mx];
int ans=-1;
int n,m;
int block[mx];
int arr[mx];
int ok;
vector<pair<int,pair<int,int>>>edges;
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++){
if(U[i]){ok=1;}
arr[V[i]]=W[i];
edges.push_back({W[i],{U[i],V[i]}});
adj[U[i]].push_back({V[i],W[i]});
adj[V[i]].push_back({U[i],W[i]});
}
for(auto it:W){
ans=max(ans,it);
}
for(int i=0;i<N;i++){
if(adj[i].size()!=2){
ans=-1;
}
}
sort(edges.begin(),edges.end());
}
int x,y;
int vis[mx];
int cost1;int targ1;
int dfs(int node,int mx){
vis[node]=1;
for(auto it:adj[node]){
if(it.first==targ1){
int z=max(mx,it.second);
ans=min(z,ans);
}
}
}
int getMinimumFuelCapacity(int x, int y) {
/*
for(int i=0;i<n;i++){
if(i!=x&&i!=y){
block[i]=1;
targ1=i;
cost1=inf;
dfs(x,0);
}
}*/
if(ok){
return ans;
}
if(x==0||y==0){
if(y==0){
swap(x,y);
}
if(adj[0].size()<3){
return -1;
}else{
ans=arr[y];
int cnt=0;
for(int i=0;i<m;i++){
if(edges[i].second.second==y){
}else if(cnt<2){
ans=max(ans,edges[i].first);
cnt++;
}else{
break;
}
}
return ans;
}
}else{
if(adj[0].size()<3){
return -1;
}else{
ans=arr[x];
ans=max(ans,arr[y]);
for(int i=0;i<m;i++){
if(edges[i].second.second==y||edges[i].second.second==x){
}else {
ans=max(ans,edges[i].first);
break;
}
}
return ans;
}
}}
/*
4 3
0 1 7
0 2 6
0 3 5
1
0 1
*/