Submission #412301

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


struct dsu{
    vi par,deg;
    vector<bool>is_line;

    dsu (int n){
        par.resize(n);
        for(int i=0; i<n; i++)
            par[i]=i;
        deg.resize(n);
        is_line.resize(n,1);
    }
    int get(int x){return par[x]=(x==par[x]?x:get(par[x]));}

    void unite(int u,int v){
        bool ok=(deg[u]+1)>2 || (deg[v]+1)>2 || get(u)==get(v);
        deg[u]++,deg[v]++;
        if(rand()%2)swap(u,v);
        if(ok)
            is_line[get(u)]=is_line[get(v)]=0;
        if(!is_line[get(u)] || !is_line[get(v)])
            is_line[get(u)]=is_line[get(v)]=0;

        u=get(u),v=get(v);
        par[u]=v;
    }

};
vector<vector<pi>> g;
vector<bool>vis;
int mx=-1;

bool cyc=1,line=1,star=1;
vvi E;

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]});
        E.pb({W[i],min(U[i],V[i]),max(U[i],V[i])});
    }
    sort(all(E));
    for(int i=0; i<n; i++)
        cyc&=g[i].size()==2,line&=g[i].size()<=2;
    line&=!cyc;
    star&=g[0].size()==n-1 && M==n-1;
}

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

}
int starr(int X,int Y){
    if(X>Y)swap(X,Y);
    int n=g.size();
    if(n<=3)return -1;

    if(X==0){
        if(E[0][2]==Y || E[1][2]==Y)
            return E[2][0];
        else return g[Y][0].second;
    }
    else{
        if(E[0][2]==X && E[1][2]==Y)
            return E[2][0];
        else if(E[0][2]==Y && E[1][2]==X)
            return E[2][0];
        else
            return max(g[X][0].second,g[Y][0].second);
    }
}

int getMinimumFuelCapacity(int X, int Y){
    if(line)return -1;
    else if(cyc)return mx-1;
    else if(star)return starr(X,Y);

    ll l=1,r=mx,ans=-1;
    int n=g.size();
    dsu d(n);
    for(int i=0; i<E.size(); i++){
        d.unite(E[i][1],E[i][2]);
        if(d.get(X)==d.get(Y) && !d.is_line[d.get(X)])
            return E[i][0];
    }
    return -1;
}

Compilation message (stderr)

swap.cpp: In function 'void init(int, int, vi, vi, vi)':
swap.cpp:81:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |     star&=g[0].size()==n-1 && M==n-1;
      |           ~~~~~~~~~~~^~~~~
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:137:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |     for(int i=0; i<E.size(); i++){
      |                  ~^~~~~~~~~
swap.cpp:134:8: warning: unused variable 'l' [-Wunused-variable]
  134 |     ll l=1,r=mx,ans=-1;
      |        ^
swap.cpp:134:12: warning: unused variable 'r' [-Wunused-variable]
  134 |     ll l=1,r=mx,ans=-1;
      |            ^
swap.cpp:134:17: warning: unused variable 'ans' [-Wunused-variable]
  134 |     ll l=1,r=mx,ans=-1;
      |                 ^~~

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