Submission #719381

#	Time	Username	Problem	Language	Result	Execution time	Memory
719381		n0sk1ll	Toll (BOI17_toll)	C++14	100 / 100	239 ms	22340 KiB

toll

#include <bits/stdc++.h>
 
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)
 
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
 
 
 
 
 
 
 
//Note to self: Check for overflow
 
struct mat
{
    vector<vector<int>> a;
    int n,m;
 
    mat()
    {
        n=0,m=0;
    }
 
    mat(int _n, int _m)
    {
        n=_n,m=_m;
        vector<int> tmp(m,mod);
        ff(i,0,n) a.pb(tmp);
    }
 
    mat operator* (mat X)
    {
        mat ret(n,X.m);
        ff(i,0,n) ff(j,0,m) ff(k,0,X.m) ret.a[i][k]=min(ret.a[i][k],a[i][j]+X.a[j][k]);
        return ret;
    }
} val[135003];
int l[135003],r[135003];
int stk=1;
 
mat neutral;
mat impo;
 
mat Sta(int p, int ll, int rr)
{
    if (ll>r[p] || rr<l[p]) return neutral;
    if (ll<=l[p] && rr>=r[p]) return val[p];
    return Sta(2*p,ll,rr)*Sta(2*p+1,ll,rr);
}
 
int main()
{
    FAST;
 
    int k,n,m,q;
    cin>>k>>n>>m>>q;
 
    neutral=mat(k,k),impo=neutral;
    ff(i,0,k) neutral.a[i][i]=0;
 
    int stn=(n+k-1)/k;
    while (stk<stn) stk*=2;
    ff(i,0,stk) l[i+stk]=i,r[i+stk]=i;
    bff(i,1,stk) l[i]=l[2*i],r[i]=r[2*i+1];
    ff(i,1,2*stk) val[i]=neutral;
    ff(i,0,stn) val[i+stk]=impo;
 
    while (m--)
    {
        int u,v,w; cin>>u>>v>>w;
        val[u/k+stk].a[u%k][v%k]=w;
    }
 
    bff(i,1,stk) val[i]=val[2*i]*val[2*i+1];
 
    while (q--)
    {
        int s,t; cin>>s>>t;
        mat T=Sta(1,s/k,t/k-1);
        if (s/k==t/k) T=impo;
        mat V(1,k);
        ff(i,0,k) V.a[0][i]=mod;
        V.a[0][s%k]=0;
        V=V*T;
        if (V.a[0][t%k]>1e9) cout<<-1<<"\n";
        else cout<<V.a[0][t%k]<<"\n";
    }
}
 
//Note to self: Check for overflow

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