这啥玩意 /bx

· · 题解

模拟赛 T3 这我哪会，做了好久。

Solution

考虑 r 全部相等怎么做。

我们维护 f(u) 表示 1\sim u 的所有路径的长度集合，这样对于每个询问只需要枚举集合判断有没有合法的长度即可。

但是这样 |f(u)| 显然是 O(V) 级别的，轻松爆了。

考虑减少状态数量，考虑这样贪心地构建状态数更少的 f'(u)：

设 v=\lfloor \frac r {p-1}\rfloor。

从小到大枚举 f(u) 中的每个 x，若 \forall y \in f'(u), y \le x + v \land \forall y' \in f(u), y' \le y \lor y' > x + v，则将 y 加入 f'(u)。

显然 f'(u) 在求答案合法性上和 f(u) 一样，证明简单。

这样直接转移 f'(u) 的复杂度是 O(p)，总复杂度 O(np)。

考虑存在 r 不同怎么办。

我们想把很多数放在一起计算，具体来说，我们把询问分成很多类，每类的 r 构成区间 [L,R]，设 v = \frac L {p - 1}，而计算这个区间的复杂度就是 O(\frac{nr}{v})。

钦定对于每个 l，取 r 为 50v 左右，可以区间数是 30 左右，直接做可以通过。

复杂度似乎是 O(np\log V)，我没去证。

Code

#include<bits/stdc++.h>
#define cir(i,a,b) for(int i=a;i<b;++i)
using namespace std;
using lint=long long;
static constexpr auto _cinl=(lint)(1e15l);
int main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int T;cin>>T;
    while(T--) [&]{
        int n,m,q,p;cin>>n>>m>>q>>p;
        vector<vector<pair<int,lint>>> vx(n);
        vector<int> inc(n);
        cir(i,0,m){
            int u,v;lint w;cin>>u>>v>>w;--u;--v;
            vx[u].emplace_back(v,w);
            ++inc[v];
        }
        auto up=1ll;
        static constexpr auto maxr=(lint)(1.1e17l);
        vector<pair<lint,lint>> vrg;
        while(up<maxr){
            const auto vw=up/(p-1)+1;
            vrg.emplace_back(up,vw*50);
            up=vw*50+1;
        }
        map<pair<lint,lint>,vector<tuple<int,int,lint>>> qs;
        string ans(q,'0');
        cir(i,0,q){
            int x;lint c;cin>>x>>c;--x;
            for(auto&[l,r]:vrg) if(l-1<c&&c-1<r) qs[{l,r}].emplace_back(i,x,c);
        }
        vector<vector<lint>> vals(n);
        vector<int> uinc;
        vector<lint> nval;
        for(auto&[l,r]:vrg) if(!(qs[{l,r}].empty())){
            const auto cv=l/(p-1);
            const auto av=r/(p-1);
            for(auto&x:vals) x.clear();
            uinc=inc;
            auto emplace=[&](vector<lint> xval,int v){
                nval=vals[v];
                for(auto&x:xval) nval.emplace_back(x);
                nval.emplace_back(r+av+7);
                inplace_merge(nval.begin(),nval.begin()+vals[v].size(),nval.end());
                auto las=-_cinl;
                vals[v].clear();
                cir(i,0,(int)(nval.size())){
                    if(nval[i]>r+av+3) break;
                    if(nval[i+1]<las+cv) continue;
                    vals[v].emplace_back(nval[i]);
                    las=nval[i];
                }
            };
            auto dfs=[&](auto __self,int u)->void {
                for(auto&[v,w]:vx[u]){
                    auto ux=vals[u];
                    for(auto&c:ux) c+=w;
                    emplace(ux,v);
                    if(!(--uinc[v])) __self(__self,v);
                }
            };
            vals[0].emplace_back(0);
            dfs(dfs,0);
            for(auto&[id,x,c]:qs[{l,r}]){
                auto uans=false;
                for(auto&w:vals[x]) uans|=(w>c-1&&w<p*c/(p-1)+1);
                ans[id]+=uans;
            }
        }
        cout<<ans<<'\n';
    }();
    return 0;
}