Submission #1107007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107007		matu	Swapping Cities (APIO20_swap)	C++17	100 / 100	151 ms	24916 KiB

swap

#include <bits/stdc++.h>
// #include <tr2/dynamic_bitset>
 
using namespace std;
// using namespace tr2;
#pragma GCC optimize("O3,unroll-loops,Ofast")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const long double eps = 1e-9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randgen(int left, int right) {
    return uniform_int_distribution<int>(left, right)(rng);
}
long long randgenll(long long left, long long right) {
    return uniform_int_distribution<long long>(left, right)(rng);
}
 
typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
struct Mint
{
    int val;
    Mint(int x = 0)
    {
        val = x % mod;
    }
    Mint(long long x)
    {
        val = x % mod;
    }
    Mint operator+(Mint oth)
    {
        return val + oth.val;
    }
    Mint operator*(Mint oth)
    {
        return 1LL * val * oth.val;
    }
    Mint operator-(Mint oth)
    {
        return val - oth.val + mod;
    }
    Mint fp(Mint a, long long n){
        Mint p = 1;
        while(n){
            if(n & 1){
                p = p * a;
            }
            a = a * a;
            n /= 2;
        }
        return p;
    }
    Mint operator/(Mint oth){
        Mint invers = fp(oth, mod - 2);
        return 1LL * val * invers.val;
    }
    friend ostream& operator << (ostream& os, const Mint& lol){
        os << lol.val;
        return os;
    }
};
 
struct AINT{
    vector<pair<ll,Mint>> aint;
    vector<pair<ll,Mint>> lazy;
    pair<ll,Mint> b;
    AINT(int n){
        b = {1e18,Mint(0)};
        aint.assign(n * 4 + 1,make_pair(1e18,Mint(0)));
        lazy.assign(n * 4 + 1, make_pair(1e18, Mint(0)));
    }
    void update(int v, int tl, int tr, int l, int r, pair<ll,Mint> val){
        if(lazy[v].first != 1e18){
            if(aint[v].first == lazy[v].first){
                aint[v].second = aint[v].second + lazy[v].second;
            }else if(aint[v].first > lazy[v].first) aint[v] = lazy[v];
 
            if(tl != tr){
                if(lazy[v * 2].first == lazy[v].first){
                    lazy[v * 2].second = lazy[v *  2].second + lazy[v].second;
                }else if(lazy[v * 2].first > lazy[v].first) lazy[v * 2] = lazy[v];
                
 
                if(lazy[v * 2 + 1].first == lazy[v].first){
                    lazy[v * 2 + 1].second = lazy[v * 2 + 1].second + lazy[v].second;
                }else if(lazy[v * 2 + 1].first > lazy[v].first){
                    lazy[v * 2 + 1] = lazy[v];
                }
            }
            lazy[v] = b;
        }
        if(l <= tl && r >= tr){
            if(aint[v].first == val.first){
                aint[v].second = aint[v].second + val.second;
            }else if(aint[v].first > val.first){
                    aint[v] = val;
            }
 
            if(tl != tr){
                if(lazy[v * 2].first == val.first){
                    lazy[v * 2].second = lazy[v *  2].second + val.second;
                }else if(lazy[v * 2].first > val.first){
                    lazy[v * 2] = val;
                }
                
 
                if(lazy[v * 2 + 1].first == val.first){
                    lazy[v * 2 + 1].second = lazy[v * 2 + 1].second + val.second;
                }else if(lazy[v * 2 + 1].first > val.first){
                    lazy[v * 2 + 1] = val;
                }
            }
            return;
        }
        if(l > tr || r < tl) return;
        int tm = (tl + tr) / 2;
        update(v * 2, tl, tm, l,r , val);
        update(v * 2 + 1, tm + 1, tr, l, r, val);
        
        if(aint[v * 2].first == aint[v * 2 + 1].first){
            aint[v] = aint[v * 2];
            aint[v].second = aint[v].second + aint[v * 2 + 1].second;
        }else{
            if(aint[v * 2].first < aint[v * 2 + 1].first) aint[v] = aint[v * 2];
            else aint[v] = aint[v * 2 + 1];
        }
 
 
    }
    pair<ll,Mint> query(int v, int tl, int tr, int l, int r){
        if(lazy[v].first != 1e18){
            if(aint[v].first == lazy[v].first){
                aint[v].second = aint[v].second + lazy[v].second;
            }else if(aint[v].first > lazy[v].first) aint[v] = lazy[v];
 
            if(tl != tr){
                if(lazy[v * 2].first == lazy[v].first){
                    lazy[v * 2].second = lazy[v *  2].second + lazy[v].second;
                }else if(lazy[v * 2].first > lazy[v].first) lazy[v * 2] = lazy[v];
                
 
                if(lazy[v * 2 + 1].first == lazy[v].first){
                    lazy[v * 2 + 1].second = lazy[v * 2 + 1].second + lazy[v].second;
                }else if(lazy[v * 2 + 1].first > lazy[v].first){
                    lazy[v * 2 + 1] = lazy[v];
                }
            }
            lazy[v] = b;
        }
        if(l <= tl && r >= tr) return aint[v];
        if(l > tr || r < tl) return make_pair(1e18,Mint(0));
        int tm = (tl + tr) / 2;
        pair<ll,Mint> p1 = query(v * 2, tl ,tm, l, r);
        pair<ll,Mint> p2 = query(v * 2 + 1, tm + 1, tr, l,r);
        if(p1.first == p2.first){
            p1.second = p1.second + p2.second;
            return p1;
        }else if(p1.first < p2.first) return p1;
        return p2;
 
        // int tm = (tl + tr) / 2;
        // if(l <= tl && r >= tr) return aint[v];
        // if(l > tr || r < tl) return 0;
        // return max(query(v * 2, tl, tm,l,r), query(v * 2 + 1, tm + 1, tr, l,r));
        
    }
};
struct AIB{
    vector<int> aib;
    AIB(int n){
        aib.assign(n + 1,0);
    
    }
    void update(int pos, int val){
        for(; pos < aib.size(); pos += (pos & -pos)){
            aib[pos] += val;
        }
    }
    int query(int pos){
        int pl = 0;
   
        for(; pos > 0; pos -= (pos & -pos)) pl += aib[pos];
        return pl;
    }
};
 
int red = 0;
int ______________________________________________________________________________________________________________________________________________;

vector<int> t,sz, deg_max, nr_edge, times, low, good;
vector<int> tin, tout;
vector<array<int,3>> pl;
int r;
void init(int n, int m, vector<int> U, vector<int> V, vector<int> W){
    pl = vector<array<int,3>>(m + 1);
    t.assign(n + 1,0);
    sz.assign(n + 1,0);
    deg_max.assign(n + 1, 0);
    times.assign(n + 1, 0);
    nr_edge.assign(n + 1, 0);
    low.assign(n + 1, 1e9);
    good.assign(n + 1,0);
    tin.assign(n + 1,0);
    tout.assign(n + 1,0);
    vector<int> deg(n + 1);
    for(int i = 1; i <= n; i++){
        t[i] = i;
        sz[i] =1;
    }
    for(int i = 1; i <= m; i++){
        pl[i] = {U[i-1] + 1,V[i-1] + 1, W[i-1]};
    }
    sort(pl.begin() + 1, pl.begin() + 1 + m, [&](array<int,3> a,array<int,3> b){
        return a[2] < b[2];
    });
    function<int(int)> root = [&](int nod){
        while(t[nod] != nod) return root(t[nod]);
        return nod;
    };
    function<void(int,int, int)> join = [&](int a, int b, int i){
        deg[a]++;
        deg[b]++;
        int ra = root(a);
        int rb = root(b);
        if(sz[ra] > sz[rb]){
            swap(ra,rb);
            swap(a,b);
        }

        if(ra != rb){
            times[ra] =i;
            deg_max[rb] = max({deg_max[rb], deg[a],deg[b], deg_max[ra]});
            good[rb] |= good[ra];
            if(deg_max[rb] > 2){
                good[rb] = 1;
                low[rb] = min(low[rb], i);
            }
            t[ra] = t[rb];
            sz[rb] += sz[ra];
        }else{
            if(!good[ra]){
                good[ra] = 1;
                low[ra] = i;;
            }
        }
    };
    for(int i = 1; i <= m; i++){
        join(pl[i][0],pl[i][1],i);
    }
    vector<vector<int>> liste(n + 1);
    for(int i = 1; i <= n; i++){
        liste[i].push_back(t[i]);
        liste[t[i]].push_back(i);
    }
    int cnt = 0;
    function<void(int,int)> dfs = [&](int nod, int p){
        tin[nod] = ++cnt;
        for(auto i : liste[nod]){
            if(i == p) continue;
            dfs(i,nod);
        }
        tout[nod] = ++cnt;
    };
    r = root(1);
    dfs(r,r);
}

int is_ancestor(int u, int v){
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int getMinimumFuelCapacity(int u, int v){
    u++;
    v++;
    
    if(!good[r]){
        return -1;
    }
    if(is_ancestor(u,v)){   


        int nod = v;
        while(t[nod] != u){
            nod = t[nod];
        }
        if(good[u]){
            return pl[max(times[nod],low[u])][2];
        }else{
            nod = u;
            while(good[t[nod]] == 0){
                nod = t[nod];
            }
            return pl[max(times[nod],low[t[nod]])][2];
        }
    }else if(is_ancestor(v,u)){
        swap(u,v);
        int nod = v;
        while(t[nod] != u){
            nod = t[nod];
        }
        if(good[u]){
            return pl[max(times[nod],low[u])][2];
        }else{
            nod = u;
            while(good[t[nod]] == 0){
                nod = t[nod];
            }
            return pl[max(times[nod],low[t[nod]])][2];
        }
    }else{

        int nod1 = v;
        while(!is_ancestor(t[nod1],u)){
            nod1 = t[nod1];
        }
        int nod2 = u;
        while(!is_ancestor(t[nod2],v)){
            nod2 = t[nod2];
        }
        if(times[nod1] < times[nod2]) swap(nod1,nod2);
        if(good[t[nod1]]){
            return pl[max(times[nod1],low[t[nod1]])][2];
        }else{
            int nod = t[nod1];
            while(!good[t[nod]]){
                nod = t[nod];
            }
            return pl[max(times[nod],low[t[nod]])][2];
        }
    }
}
// int32_t main(){
//     cin.tie(0)->sync_with_stdio(0);
//     // int t = 1; 
//     // if(red) cin >> t;
   
//     // // while(t--){
//     // //     solve();
//     // // }
 
//     init(3,2,{0,0},{1,2},{5,5});
//     cout << getMinimumFuelCapacity(1,2) << '\n';

// }
 
 
/*
 
2 2 2 2 4
1 3 5
 
 
1 30
1 40
120 2 
2 430
100 3 
3 30
100 4 
4 490
100 5 
5 440
40 6 
6 290
50 7 
7 190
290 8 
8 430
50 9 
9 60
190 10 
10 490
*/

Compilation message (stderr)

swap.cpp: In member function 'void AIB::update(int, int)':
swap.cpp:176:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |         for(; pos < aib.size(); pos += (pos & -pos)){
      |               ~~~~^~~~~~~~~~~~

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