Submission #1136411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136411		friedel	Toll (BOI17_toll)	C++20	100 / 100	141 ms	73544 KiB

toll

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using llu=unsigned long long;
using ll=long long;
using ld=long double;
using pir=pair<ll,ll>;
using vl=vector<ll>;
using sl=set<ll>;
using msl=multiset<ll>;
using prq=priority_queue<ll>;
using prqi=priority_queue<ll,vector<ll>,greater<ll>>;
using ma=map<ll,ll>;
using vp=vector<pair<ll,ll>>;
using vvl=vector<vector<ll>>;
using vvvl=vector<vector<vector<ll>>>;
using vvp=vector<vector<pair<ll,ll>>>;
using sp=set<pair<ll,ll>>;
using msp=multiset<pair<ll,ll>>;
#define nfs string::npos
#define count1(n) __builtin_popcountll(n)
#define last1(n) __builtin_ctzll(n)
#define first1(n) 63-__builtin_clzll(n)
#define maxi(v) max_element(all(v))
#define mini(v) min_element(all(v))
#define lb(n) lower_bound(n)
#define ub(n) upper_bound(n)
#define lbd(v,n) lower_bound(all(v),n)
#define ubd(v,n) upper_bound(all(v),n)
#define bins(v,n) binary_search(all(v),n)
#define fr(i,a,b) for(i=a;i<=b;i++)
#define fv(i,a,b) for(i=a;i>=b;i--)
#define f(i,n) for(i=0;i<n;i++)
#define fn(i,n) for(i=n-1;i>=0;i--)
#define pb push_back
#define ppb pop_back
#define all(v) v.begin(),v.end()
#define g(v,n) vl v(n); f(_,n) cin>>v[_]
#define bs(n,x) bitset<n> (x).to_string()
#define invp(v,n) vp v;f(_,n) cin>>v[_].first>>v[_].second
#define seev(v) for(auto ggg:v) cout<<ggg<<"-"
#define print(v) for(auto ggg:v) cout<<ggg<<" "
const ll inf=4e10;
const ll mod=1000000007;
const ll mod2=998244353;

ll power(ll a,ll b,ll p=inf)
{
    ll res=1;a%=p;
    while(b>0)
    {
        if(b%2==1)
            res=(res*a)%p;
        a=(a*a)%p;
        b=b/2;
    }
    return res;
}
ll log(ll n,ll k)
{
    ll a=k,b=0;
    while(a<=n)
        a*=k,b++;
    return b;
}
ll todec(ll n,string s)
{
    ll i,k=0;
    f(i,n)
        if(s[i]=='1')
            k+=1LL<<(n-i-1);
    return k;
}
bool vps(const pair<ll,ll> &a,const pair<ll,ll> &b)
{
    return (a.second<b.second);
}
bool fts(const pair<ll,ll> &a,const pair<ll,ll> &b)
{
    if(a.first!=b.first)
        return (a.first<b.first);
    return (a.second>b.second);
}

void solve(ll tc)
{
    ll n,m,k=0,j=0,i=0,x=0,y=0,z=0,p=0,q=0,l=0,sum=0,temp=1,flag=0,a=0,b=0,c=0,d=1,r=0,mn=inf,mx=-inf,_,__,mid;
    string s1,s2,s3,s;char ch;
    cin>>k>>n>>m>>q;
    p=n/k+1;
    vector<vvvl> v(16,vvvl(p,vvl(k,vl(k,inf))));
    f(i,m)
    {
        cin>>x>>y>>d;
        v[0][x/k][x%k][y%k]=d;
    }
    fr(j,1,15)
        f(i,p)
            if(i+(1ll<<(j-1))<p)
                f(a,k)
                    f(b,k)
                        f(c,k)
                            v[j][i][a][c]=min(v[j][i][a][c],v[j-1][i][a][b]+v[j-1][i+(1ll<<(j-1))][b][c]);
    while(q--)
    {
        cin>>x>>y;
        d=y/k-x/k;
        i=x/k;
        vvl ans(k,vl(k,inf));
        f(a,k)
        ans[a][x%k]=0;
        fn(j,16)
        {
            if((1ll<<j)<=d)
            {
                vvl tp(k,vl(k,inf));
                f(a,k)
                {
                    f(b,k)
                    {
                        f(c,k)
                        {
                            tp[a][c]=min(tp[a][c],ans[a][b]+v[j][i][b][c]);
                        }
                    }
                }
                ans=tp;
                d-=1ll<<j;
                i+=1ll<<j;
            }
        }
        if(ans[x%k][y%k]>=inf)
            cout<<-1<<endl;
        else
            cout<<ans[x%k][y%k]<<endl;
    }
}

//Use variables correctly
//Check for boundary conditions
//Write the step statement in while loops
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    ll t=1;
//    cin>>t;
    while(t--)
    {
        solve(t);
//        cout<<endl;
    }
    return 0;
}

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