Submission #412203

#	Time	Username	Problem	Language	Result	Execution time	Memory
412203		Carmel_Ab1	Swapping Cities (APIO20_swap)	C++17	17 / 100	2073 ms	45924 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

umap<int,umap<int,int>>c;
vvi g;
void init(int n, int M,vi U,vi V,vi W){
    g.resize(n);
    for(int i=0; i<M; i++){
        g[U[i]].pb(V[i]);
        g[V[i]].pb(U[i]);
        c[U[i]][V[i]]=c[V[i]][U[i]]=W[i];
    }
}

bool ans;
void dfs(vvi &g,vector<bool>& vis,int src,int par){
    vis[src]=1;
    for(int nbr:g[src]) {
        if(nbr==par)continue;
        if(vis[nbr])ans=1;
        else dfs(g,vis,nbr,src);
        if(g[src].size()>2)ans=1;
    }
}
bool ok(int x,int y,int w){
    int n=g.size();
    vvi gt(n);
    for(int i=0; i<n; i++)
        for(int j=0; j<g[i].size(); j++)
            if(c[i][g[i][j]]<=w)
                gt[i].pb(g[i][j]);
    vi prv(n,-1),deg(n);
    vector<bool>vis(n);
    ans=0;
    dfs(gt,vis,x,-1);
    if(!vis[y])return 0;
    return ans;

}

int getMinimumFuelCapacity(int X, int Y){
    ll l=1,r=1e9,ans=-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;
}

Compilation message (stderr)

swap.cpp: In function 'bool ok(int, int, int)':
swap.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int j=0; j<g[i].size(); j++)
      |                      ~^~~~~~~~~~~~

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