Submission #412247

#	Time	Username	Problem	Language	Result	Execution time	Memory
412247		Carmel_Ab1	Swapping Cities (APIO20_swap)	C++17	0 / 100	2069 ms	14320 KiB

swap

#include<bits/stdc++.h>
#include "swap.h"

//#include "grader.cpp"

using namespace std;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int>vi;
typedef vector<vector<int>>vvi;
typedef vector<ll>vl;
typedef vector<vl> vvl;
typedef pair<int,int>pi;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld,ld> pld;
//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T> ostream& operator<<(ostream& os, vector<T>& a){os<<"[";for(int i=0; i<ll(a.size()); i++){os << a[i] << ((i!=ll(a.size()-1)?" ":""));}os << "]\n"; return os;}

#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map


vector<vector<pi>> g;
vector<bool>vis;
int mx=-1;
void init(int n, int M,vi U,vi V,vi W){
    g.resize(n);
    vis.resize(n);
    mx=*max_element(all(W))+1;
    for(int i=0; i<M; i++){
        g[U[i]].pb({V[i],W[i]});
        g[V[i]].pb({U[i],W[i]});
    }
}

bool ans;
void dfs(int src,int par,int w){
    if(ans)return;
    vis[src]=1;
    int cnt=0;
    for(pi nbr:g[src]) {
        if(nbr.first==par || nbr.second>w)continue;
        if(vis[nbr.first])ans=1;
        if(nbr.second<=w)cnt++;
        if(cnt>2){
            ans=1;
            return;
        }
        else if(!ans)dfs(nbr.first,src,w);
    }
}
bool ok(int x,int y,int w){
    int n=g.size();
    vis.assign(n,0);
    ans=0;
    dfs(x,-1,w);
    if(!vis[y])return 0;
    return ans;

}

int getMinimumFuelCapacity(int X, int Y){
    ll l=1,r=mx,ans=-1;
    if(!ok(X,Y,mx))
        return -1;
    while(l<=r){
        ll m=(l+r)/2;
        if(ok(X,Y,m))
            ans=m,r=m-1;
        else
            l=m+1;
    }
    return ans;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27