Submission #392061

#	Time	Username	Problem	Language	Result	Execution time	Memory
392061		Jarif_Rahman	Swapping Cities (APIO20_swap)	C++17	6 / 100	2072 ms	36864 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf = 1.5e9;

struct segtree{
    
    int k;
    vector<pair<int, int>> mn;
    segtree(int n){
        k = 1;
        while(k <= n) k*=2; k*=2;
        mn.assign(k, {inf,0});
        for(int i = 0; i < k/2; i++) mn[i+k/2].sc = i;
        for(int i = k/2; i > 0; i--) mn[i].sc = mn[2*i].sc;
    }
    void upd(int in, pair<int, int> x){
        in+=k/2;
        mn[in] = x, in/=2;
        while(in > 0){
            mn[in] = min(mn[2*in], mn[2*in+1]);
            in/=2;
        }
    }
    pair<int, int> smn(int l, int r, int nd, int a, int b){
        if(b < l || a > r) return {inf, inf};
        if(a >= l && b <= r) return mn[nd];
        int c = (a+b)/2;
        return min(smn(l, r, 2*nd, a, c), smn(l, r, 2*nd+1, c+1, b));
    }
    pair<int, int> smn(int l, int r){
        return smn(l, r, 1, 0, k/2-1);
    }
}seg(10);

struct reachability_tree{
    int n;
    vector<int> p;
    vector<int> adj;
    vector<bool> ok;
    vector<vector<int>> v;
    vector<int> w;
    reachability_tree(int n){
        reachability_tree::n = n;
        v.resize(n);
        p.resize(n);
        ok.resize(n, 0);
        adj.resize(n, 0);
        w.resize(n);
        for(int i = 0; i < n; i++) p[i] = i;
    }
    int get(int x){
        if(p[x] == x) return x;
        return get(p[x]);
    }
    void unite(int a, int b, int vl){
        int aa = a, bb = b;
        a = get(a), b = get(b);
        adj[aa]++;
        adj[bb]++;
        p.pb(n);
        ok.pb(0);
        v.pb({});
        p[a] = n;
        p[b] = n;
        v[n].pb(a);
        if(a != b) v[n].pb(b);
        ok[n] = ok[a]|ok[b];
        if(max(adj[aa], adj[bb]) >= 3 || a == b) ok[n] = 1;
        n++;
        w.pb(vl);
    }
}rt(0);


int n, m;
vector<int> depth, ett, pos, anc;

void dfs(int nd, int d, int ls){
    depth[nd] = d;
    ett.pb(nd);
    if(rt.ok[nd]) ls = nd;
    anc[nd] = ls;
    for(int x: rt.v[nd]){
        dfs(x, d+1, ls);
        ett.pb(nd);
    }
}

void init(int n, int m, vector<int> u, vector<int>v, vector<int>w){
    ::n = n, ::m = m;
    rt = reachability_tree(n);
    vector<tuple<int, int, int>> edges;
    for(int i = 0; i < m; i++){
        edges.pb({w[i], u[i], v[i]});
    }
    sort(edges.begin(), edges.end());
    for(auto [wi, ui, vi]: edges) rt.unite(ui, vi, wi);
    depth.resize(rt.n);
    pos.resize(rt.n);
    anc.resize(rt.n);
    dfs(rt.get(0), 1, -1);
    seg = segtree(ett.size());
    for(int i = 0; i < ett.size(); i++) seg.upd(i, {depth[ett[i]], ett[i]});
    for(int i = 0; i < rt.n; i++) pos[ett[i]] = i;
}

int getMinimumFuelCapacity(int x, int y){
    x = pos[x], y = pos[y];
    if(x > y) swap(x, y);
    int lca = seg.smn(x, y).sc;
    int ans = anc[lca];
    if(ans != -1) ans  = rt.w[ans];
    return ans;
}

Compilation message (stderr)

swap.cpp: In constructor 'segtree::segtree(int)':
swap.cpp:17:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   17 |         while(k <= n) k*=2; k*=2;
      |         ^~~~~
swap.cpp:17:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   17 |         while(k <= n) k*=2; k*=2;
      |                             ^
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:109:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for(int i = 0; i < ett.size(); i++) seg.upd(i, {depth[ett[i]], ett[i]});
      |                    ~~^~~~~~~~~~~~

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