这啥玩意 /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

CPP

#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;
}

文章操作

Solution

Code

相关推荐

评论

这啥玩意 /bx