Submission #1133730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133730		krishbansal333	Toll (BOI17_toll)	C++20	100 / 100	357 ms	85076 KiB

toll

/*
Krishbansal333
Created: 08.01.2025  19:56:12
*/
 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

#define ll long long
#define ld long double
#define ull uint_fast64_t
#define all(v) v.begin(),v.end()
#define maxi(v) max_element(all(v))
#define mini(v) min_element(all(v))
#define f(i,n) for(ll i = 0; i < n; i++)
#define vi vector<ll>
#define ipa(arr) for(ll i = 0; i < sizeof(arr)/sizeof(arr[0]); i++) cin>>arr[i];
#define ipv(arr) for(ll i = 0; i < (int) arr.size(); i++) cin>>arr[i];
#define line cout<<endl; 
#define nl "\n"
#define mp map<ll,ll>
#define st set<ll> 
#define pii pair<ll,ll>
#define vv vector<vector<ll>>
#define vvpi vector<vector<pair<ll,ll>>>
#define vpi vector<pair<ll,ll>>
#define pb push_back
#define F first
#define S second
#define fr(i,k,n) for(ll i = k; i < n; i++)
#define fv(i,k,n) for(ll i = n-1; i >=k; i--)
#define nah cout<<"NO\n";return;
#define naah cout<<"-1\n";return;
#define yeah cout<<"YES\n";return;

const ll MOD = 1e9+7;
const ll MOD2 = 998244353;
const ll INF = 1e16;
const ll MAXN = 10000001;
const ld PI = acos((ld)-1);

using namespace std;
//using namespace __gnu_pbds;


vector<ll> spf;
vector<ll> phi;

#ifndef ONLINE_JUDGE  
#define debug(x) cout << endl << #x<<" "; _print(x); cout << endl;  
#define debuga(x,a) cout << endl << #x<<" [ "; for(ll i=0 ; i <a; i++) { _print(x[i]); cout<<" "; } cout<<"]"<<endl;
#else 
#define debug(x)  
#define debuga(x,a) 
#endif
void _print(ll t) {cout << t;}
void _print(int t) {cout << t;}
void _print(string t) {cout << t;}
void _print(char t) {cout << t;}
void _print(ld t) {cout << t;}
void _print(double t) {cout << t;}
void _print(ull t) {cout << t;}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cout << "{"; _print(p.F); cout << ","; _print(p.S); cout << "}";}
template <class T> void _print(vector <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T> void _print(set <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T> void _print(multiset <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T, class V> void _print(map <T, V> v) {cout << "[ "; for (auto i : v) {_print(i); cout << " ";} cout << "]";}
// struct chash { const uint64_t C = uint64_t(2e18 * PI) + 71; const uint32_t RANDOM = chrono::steady_clock::now().time_since_epoch().count(); size_t operator()(uint64_t x) const { return __builtin_bswap64((x ^ RANDOM) * C); }};

ll interact(ll a, ll b)
{
   cout << "? " << a << " " << b << endl;   cout.flush();
   ll res = 0; cin >> res ; return res;
}
ll cdiv(ll a,ll b)
{
    return (a + b - 1) / b;
}

// **phii**
void phii(ll n) {
    phi.assign(n + 1LL,0);
    phi[0] = 0;
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
        phi[i] = i - 1;

    for (int i = 2; i <= n; i++)
        for (int j = 2 * i; j <= n; j += i)
              phi[j] -= phi[i];
}
// **phii**


//**SIEVE**
// Time Complexity : O(nloglogn)
void sieve(ll n)
{
    spf.assign(n+1,1);
    spf[0] = 0;
    for (ll i = 2; i <= n; i++) {
        if (spf[i] == 1) { 
            for (ll j = i; j <= n; j += i) {
                if (spf[j]== 1)
                    spf[j] = i;
            }
        }
    }
}

vector<ll> getFactorization(ll x)
{
    vector<ll> ret;
    while (x != 1) {
        ret.push_back(spf[x]);
        x = x / spf[x];
    }
    return ret;
}
//**SIEVE**

//**FIBONACCI NUMBBERS**
struct matrix {
    long long mat[2][2];
    matrix friend operator *(const matrix &a, const matrix &b){
        matrix c;
        for (int i = 0; i < 2; i++) {
          for (int j = 0; j < 2; j++) {
              c.mat[i][j] = 0;
              for (int k = 0; k < 2; k++) {
                  c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
              }
          }
        }
        return c;
    }
};
matrix matpow(matrix base, long long n) {
    matrix ans{ {
      {1, 0},
      {0, 1}
    } };
    while (n) {
        if(n&1)
            ans = ans*base;
        base = base*base;
        n >>= 1;
    }
    return ans;
}
long long fib(int n) {
    matrix base{ {
      {1, 1},
      {1, 0}
    } };
    return matpow(base, n).mat[0][1];
}
//**FIBONACCI NUMBBERS**

//**BINNARY EXPOO**

long long binpow(long long a, long long b, ll m) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            {   
                res = (res * a);
                if(res>=m) res = res%m+m;
            }

        a =(a * a);
        if(a>=m)  a=a%m+m;
        b >>= 1;
    }
    return res%m;
}
long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            {   
                res = (res * a);
            }
        a =(a * a);
        b >>= 1;
    }
    return res;
}
//**BINNARY EXPOO**

//**Mat power**
typedef vector<vector<ll>> Matrix;

Matrix mult(Matrix &a, Matrix &b) 
{
    ll n = a.size();
    ll m = b[0].size();
    ll p = b.size();
 
    Matrix result(n,vi(m,0));
 
    f(i,n)
        f(j,m)
            f(k,p)
                result[i][j] = (result[i][j] + (a[i][k]*b[k][j])%MOD)%MOD;
    
    return result;
}
 
Matrix matpow(Matrix &matrix, ll n) 
{
    ll sz = matrix.size();
    Matrix result(sz,vi(sz));
    f(i,sz)    result[i][i] = 1;
 
    if (n == 0LL) return result;
 
    if (n == 1LL) return matrix;
 
    Matrix temp = matpow(matrix, n / 2LL);
    result = mult(temp, temp);
 
    if (n % 2LL == 1LL) result = mult(result, matrix);
    return result;
}
//**Mat power**

//**Unionfind**
struct dsu{
    vector <int> root, sz;
    int n;
 
    dsu(int nn){
        n = nn;
        root.resize(n + 1);
        sz.resize(n + 1, 1);
        for (int i = 1; i <= n; i++) root[i] = i;
    }
 
    int find(int x){
        if (root[x] == x) return x;
        return root[x] = find(root[x]);
    }
 
    bool unite(int x, int y){
        x = find(x); y = find(y);
        if (x == y) return false;
 
        if (sz[y] > sz[x]) swap(x, y);
        sz[x] += sz[y];
        root[y] = x;
        return true;
    }
};
 
struct unionFind
{
    vector<int> p,score,lzy;
    vector<vi> rank;
    
 
        unionFind(int n)
        {
            rank.assign(n,vi()); p.assign(n,0);score.assign(n,0);lzy.assign(n,0);
            iota(p.begin(),p.end(),0);
            f(i,n) rank[i].push_back(i);
        }
 
        int findSet(int i){ return (p[i] == i) ? i :p[i] =  findSet(p[i]);}
 
        bool isSameSet(int i, int j){ return findSet(i) == findSet(j);}

        void add(ll i, ll v)
        {
            ll x =findSet(i);
            lzy[x] +=v;

        }
        ll get(ll i)
        {
            int x = findSet(i);
            return score[i]+lzy[x];
        }
        void unionSet(int i, int j)
        {
            
            int x = findSet(i), y = findSet(j);
            if(x==y) return;

            if(rank[x].size() > rank[y].size()) {
                
                p[y] = x;
                for(auto i:rank[y])
                {
                    rank[x].push_back(i);
                }
                for(auto i:rank[y])
                {
                    score[i]+=lzy[y]-lzy[x];
                }
                
                lzy[y] =0;
                rank[y].clear();

            }
            else 
            {
                p[x] = y;
                for(auto i:rank[x])
                {
                    rank[y].push_back(i);
                }
                for(auto i:rank[x])
                {
                    score[i]+=lzy[x]-lzy[y];
                }
                lzy[x] =0;
                rank[x].clear();
            }
            
        }
};

//**Unionfind**

//**Segtree**
struct segtree {
    // to reduce memory, use left node as v + 1, right node as v + (mid - l + 1) << 1

    struct node {
        ll val = 0;
        node() : val(0ll) {}
        node(ll val_) : val(val_) {}
        node operator+(const node &a) {
            return {this -> val + a.val};
        }
    };
    int n;
    vector<ll> a; vector<node> sgt;

    
    // segtree(int n_) : n(n_), sgt(vector(n_ << 2, node())), a(vector(n_, 0ll)) {}

    segtree(vector<ll> a_) {
        n = a_.size();
        sgt.resize(n << 2), a = a_;
    
        auto build = [&](int v, int tl, int tr, auto self) -> void 
        {
            if(tl == tr) sgt[v] = apply(a[tl]);

            else {
                int tm = (tl + tr) >> 1;
                self(v << 1, tl, tm, self); self((v << 1) | 1, tm + 1, tr, self);
                sgt[v] = sgt[v << 1] + sgt[(v << 1) | 1];
            }
        };
        build(1, 0, n - 1, build);
    }
    node rquery(int v, int tl, int tr, int l, int r) {
        if(tl == l && tr == r) return sgt[v];
        else if(l > r) return def();
        else{
            int tm = (tl + tr) >> 1;
            node leftans = rquery(v << 1, tl, tm, l, min(tm, r));
            node rightans = rquery((v << 1) | 1, tm + 1, tr, max(l, tm + 1), r);
            return leftans + rightans;
        }
    }
    void pupdate(int v, int tl, int tr, int pos, ll x) {
        if(tl == tr)
            sgt[v] = apply(x);
        else{
            int tm = (tl + tr) >> 1;
            if(pos <= tm) pupdate(v << 1, tl, tm, pos, x);
            else pupdate((v << 1) | 1, tm + 1, tr, pos, x);
            sgt[v] = sgt[v << 1] + sgt[(v << 1) + 1];
        }
    }
    
    ll query(int l, int r) {
        return rquery(1, 0, n - 1, l, r).val;
    }
    void update(int i, ll x){
        pupdate(1, 0, n - 1, i, x);
    }
    static node apply(ll val) {
        return node(val);
    }
    
    node def() {
        return node(0);
    }
};
//**Segtree**


//** lazy segtree **
struct segtreelazy {
    struct node {
        // edit this
        ll val = 0;
        ll lazy = 0;
        node() : val(0ll), lazy(0ll) {}
        node(ll val_, ll lazy_) : val(val_), lazy(lazy_) {}
        node operator+(const node &a) {
            return { this -> val + a.val, 0ll };
        }
    };
    int n;
    vector<ll> a; vector<node> sgt;
    
    segtreelazy(vector<ll> a_) {
        n = a_.size();
        sgt.resize(n << 2), a = a_;
        auto build = [&](int v, int tl, int tr, auto self) -> void {
            if(tl == tr) sgt[v] = apply(a[tl]);
            else {
                int tm = (tl + tr) >> 1;
                self(v << 1, tl, tm, self); self((v << 1) | 1, tm + 1, tr, self);
                sgt[v] = sgt[v << 1] + sgt[(v << 1) | 1];
            }
        };
        build(1, 0, n - 1, build);
    }
    
    node rquery(int v, int tl, int tr, int l, int r) {
        if(tl == l && tr == r) return sgt[v];
        else if(l > r) return def();
        else{
            push(v);
            int tm = (tl + tr) >> 1;
            node leftans = rquery(v << 1, tl, tm, l, min(tm, r));
            node rightans = rquery((v << 1) | 1, tm + 1, tr, max(l, tm + 1), r);
            return leftans + rightans;
        }
    }
    void rupdate(int v, int tl, int tr, int l, int r, ll x) {
        if(tl == l && tr == r)
            upd(v, x);
        else if(l <= r){
            push(v);
            int tm = (tl + tr) >> 1;
            rupdate(v << 1, tl, tm, l, min(r, tm), x);
            rupdate((v << 1) | 1, tm + 1, tr, max(l, tm + 1), r, x);
            sgt[v] = sgt[v << 1] + sgt[(v << 1) + 1];
        }
    }
    ll query(int l, int r) {
        return rquery(1, 0, n - 1, l, r).val;
    }
    void update(int l, int r, ll x){
        rupdate(1, 0, n - 1, l, r, x);
    }

    void push(int v) {
        upd(v << 1, sgt[v].lazy); upd((v << 1) | 1, sgt[v].lazy);
        sgt[v].lazy = 0;
    }
    void upd(int v, ll x) {
        // edit this
        // do not forget to update lazy here ( sgt[v]+=x )

        sgt[v].val += x;
        sgt[v].lazy += x;
    }
    static node apply(ll val) {
        // edit this;
        return node(val, 0ll);
    }
    node def() {
        // edit this
        return node(0ll, 0ll);
    }
};
//** lazy segtree **

//**lca**
ll k,n,sz;
//**lca**
struct node
{
    ll val;
    vv mat;
    node() {
        val = sz+2;
        mat.assign(k,vi(k,INF));
    }
};

void _print(node t) {
    debug(t.val);
    debug(t.mat);
}
//Add Modulo.
void solve(){
    ll m,d,x,y,z;bool b,flag; string s; mp mm; st se; vi v;
    cin>>k>>n>>m>>d;
    vvpi graph(n+10);
    f(i,m)
    {
        cin>>x>>y>>z;
        graph[x].pb({y,z});
    }

    sz = ceil((n+10)*1.0/k);
    ll l = ceil(log2(sz));
    vector<vector<node>> up(sz+3,vector<node>(l+1));
    
    auto combine = [&](node a, node b)->node
    {
        node ans;
        ans.val = b.val;
        vv mat(k,vi(k,INF));
        f(i,k)
        {
            f(j,k)
            {
                ll res = INF;
                f(p,k)
                {
                    res = min(res,a.mat[i][p]+b.mat[p][j]);
                }
                mat[i][j]=res;
            }
        }
        ans.mat =mat;
        return ans;
    };
    // debug(up);
    fv(i,0,sz-1)
    {
        vv mat(k,vi(k,INF));
        f(j,k)
        { 
            for(auto [x,y]:graph[i*k+j])
            {
                mat[j][x%k] = min(y,mat[j][x%k]);
                
            }
        }
        node kri;
        kri.val = i+1;
        kri.mat = mat; 
        up[i][0] = kri;
        for(int j = 1; j <= l; ++j)
        {
            up[i][j] = combine(up[i][j-1],up[(up[i][j-1].val)][j-1]);
        }   
    }
    // debug(up);
   
    while(d--)
    {
        cin>>x>>y;
        
        ll lg=x/k,rg=y/k;
        ll lv=x%k,rv=y%k;
        if(y<x) {cout<<"-1\n";continue;}
        if(rg==lg && lv!=rv) {cout<<"-1\n";continue;}
        ll res =0;
        node curr;
        curr.val = lg;
        curr.mat.assign(k,vi(k,0));
        for (int i = l; i >= 0; --i) {
            
            if(curr.val + (1 << i) <= rg)
            {
                if(curr.val == lg) curr = up[curr.val][i];
                else curr = combine(curr,up[curr.val][i]);
            }
            // debug(curr.mat)
        }
        // debug(curr.mat)
        cout<<((curr.mat[lv][rv] >= INF-100000) ? -1:curr.mat[lv][rv] )<<endl;
    }
}



int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // memset(dp,-1,sizeof(dp));
    
    ll t =1;
    // cin>>t;
    while(t--){
    solve();
    }
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44