제출 #1134847

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1134847		darsh_jain_me	Toll (BOI17_toll)	C++20	100 / 100	357 ms	310580 KiB

toll

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define fr(j, l,n) for(int j = l; j < int(n); j++)
#define fn(j,n,l) for(int j=n-1;j>=l;j--) 
#define gets(s) string s; cin>>s;
#define all(v) v.begin(),v.end()
#define getv(v,n) vector<ll> v(n); fr(i,0,n) cin >> v[i];
#define seev(a) for(auto x:a){cout<<x<<" ";}cout<<endl;
#define vl vector<ll>
#define ve vector
#define vvl vector<vector<ll>>
#define vp vector<pair<ll,ll>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define pb push_back
#define mp make_pair
#define mse multiset<ll>
#define se set<ll>
#define ma map<ll,ll>
#define getmat(v,n,m) vector<vl>v(n,vl(m));fr(i,0,n) {fr (j,0,m) cin>>v[i][j];}
#define seemat(mat) for(auto row:mat){seev(row);}
#define YES cout<<"YES\n";
#define NO cout<<"NO\n";
using namespace std;
using namespace __gnu_pbds;

// Define ordered multiset with long long

typedef tree<long long, long long, less<long>, rb_tree_tag, tree_order_statistics_node_update> ordered_multimap;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

vl sieve;
void SieveOfEratosthenes(int n)
{
    // Create a boolean array "prime[0..n]" and initialize
    // all entries it as true. A value in prime[i] will
    // finally be false if i is Not a prime, else true.
    vl prime(n+1,true);
 
    for (int p = 2; p * p <= n; p++) {
        // If prime[p] is not changed, then it is a prime
        if (prime[p] == true) {
            // Update all multiples of p greater than or
            // equal to the square of it numbers which are
            // multiple of p and are less than p^2 are
            // already been marked.
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
 
    // Print all prime numbers
    for (int p = 2; p <= n; p++)
        if (prime[p])
            sieve.push_back(p);
}
bool sortbysec(const pair<ll, ll>& a,
               const pair<ll, ll>& b)
{
    return (a.second < b.second);
}
// gives gcd and the other coefficients
ll gcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll x1, y1;
    ll d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}
// a raised to power b
ll pwr(ll a, ll b, ll mod = 0){
    ll result = 1;
    if(mod == 0){
        while(b){
            if(b & 1) result *= a;
            a *= a;
            b = b >> 1;
        }
    }
    else {
        while(b){
            if(b & 1){
                result *= a;
                result  = result % mod;
            }
            a *= a;
            a = a % mod;
            b = b >> 1;
        }
    }
    return result;
}
ll modularinverse(ll a,ll p)// p is prime
{
    return pwr(a,p-2,p);
}
// to convert string to binary(63 bits)
string tobin(ll a)
{
    string s;
    for (int i = 0; i < 63; i++)
    {
        if(a%2==1)
        {
            s+='1';
        }
        else
        {
            s+='0';
        }
        a>>=1;
    }
    return s;
}
int log2_floor(unsigned long long i) {
    return i ? 63 - __builtin_clzll(i) : -1;
    // -1 as log undefined for 0
}
// QUESTION DHANG SE PADHNA
void combine(vvl &a, vvl &b, ll &k, vvl &c)
{
    for (int i = 0; i < k; i++)
    {
        for (int j = 0; j < k; j++)
        {
            for (int jj = 0; jj < k; jj++)
            {
                c[i][j]=min(c[i][j],a[i][jj]+b[jj][j]);
            }
        }
        
        
    }
    
}
void solve(ll tc){
    ll n=0,m=0,k=0,a=0,b=0,c=0,x=0,y=0,z=0,o;
    cin>>k>>n>>m>>o;
    ve<vp> gr(n);
    ve<ve<vvl>>dist(n,ve<vvl> (log2_floor(n)+1,vvl(5,vl(5,1e18))));
    for (int i = 0; i < m; i++)
    {
        cin>>a>>b>>x;
        // gr[a].pb({b,x});
        dist[a/k][0][a%k][b%k]=x;
    }
    // cout<<'w'<<endl;
    for(int j=0;j<dist[0].size()-1;j++)
    {
        for (int i = 0; i < n/k; i++)
        {
            if((i+(1<<(j)))<n)
            {
                // cout<<i<<' '<<(1<<j)<<endl;
                combine(dist[i][j],dist[(i+(1<<(j)))][j],k,dist[i][j+1]);
            }
        }
    }
    // for (int i = 0; i < n; i++)
    // {
    //     cout<<i<<' '<<endl;
    //     // vvl ans(k,vl(k,1e18));
    //     // combine(dist[i][0],dist[i+1][0],k,ans);
    //     // seemat(ans);
    //     // cout<<endl;
    //     seemat(dist[i][1]);

    // }
    for (int i = 0; i < o; i++)
    {
        cin>>x>>y;
        vvl ans(k,vl(k, 1e18));
        vvl ans2(k,vl(k, 1e18));
        for (int i = 0; i < k; i++)
        {
            ans2[i][i]=0;
        }
        c=x/k,z=y/k;
        ll inix=x,iniy=y;
        for (int j = 0; j < dist[0].size(); j++)
        {
            // cout<<z<<' '<<c<<endl;
            if(((z-c) &  (1<<j)))
            {
                combine(ans2,dist[c][j],k,ans);
                // x+=1<<j;
                c+=(1<<j);
                swap(ans2,ans);
                for (int jj = 0; jj < k; jj++)
                {
                    for (int ii = 0; ii < k; ii++)
                    {
                        ans[jj][ii]=1e18;
                    }
                }
            }
        }
        // seemat(ans2);
        if(inix/k==iniy/k)
        {
            cout<<-1<<endl;
        }
        else
        {
            if(ans2[inix%k][iniy%k]==1e18)
            {
                cout<<-1<<endl;
            }
            else
            {
                cout<<ans2[inix%k][iniy%k]<<endl;
            }
        }
    }
    

}


int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int t=1;
// cin>>t;
ll tc=0;
while(t--){
    tc++;
    solve(tc);
}

return 0;
}

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