QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#310781#6404. Shuttle TourPlentyOfPenaltyWA 102ms155236kbC++174.1kb2024-01-21 17:42:352024-01-21 17:42:35

Judging History

你现在查看的是最新测评结果

  • [2024-01-21 17:42:35]
  • 评测
  • 测评结果:WA
  • 用时:102ms
  • 内存:155236kb
  • [2024-01-21 17:42:35]
  • 提交

answer

#include "bits/stdc++.h"
typedef long long ll;
typedef unsigned un;
using namespace std;
typedef std::pair<ll,ll> pll;
typedef std::pair<int,ll> pil;
const int MAXN = 200011,INF = 1e9+233;

pll merge(pll a,pll b){return pll(max(a.first,b.first),min(a.second,b.second));}
int n,q;
struct Segment_Tree
{
    struct node
    {
        ll maxv,minv;
    }t[MAXN<<2|1];
    #define rt t[num]
    void pushup(un num)
    {
        rt.maxv=max(t[num<<1].maxv,t[num<<1|1].maxv);
        rt.minv=min(t[num<<1].minv,t[num<<1|1].minv);
    }
    void build(un l=1,un r=n,un num=1)
    {
        if(l==r)
        {
            // if(arr[l]==-1)rt.maxv=0,rt.minv=INF;
            // else rt.maxv=rt.minv=arr[l];
            rt.maxv=0,rt.minv=INF;
            return;
        }
        un mid=(l+r)>>1;
        build(l,mid,num<<1),build(mid+1,r,num<<1|1);
        pushup(num);
    }
    void modify(un pos,ll val,un l=1,un r=n,un num=1)
    {
        if(l==r)
        {
            if(val==-1)rt.maxv=0,rt.minv=INF;
            else rt.maxv=rt.minv=val;
            return;
        }
        un mid=(l+r)>>1;
        if(pos<=mid)modify(pos,val,l,mid,num<<1);
        else modify(pos,val,mid+1,r,num<<1|1);
        pushup(num);
    }
    pll Query(un ql,un qr,un l=1,un r=n,un num=1)
    {
        if(ql<=l&&r<=qr)return pll(rt.maxv,rt.minv);
        pll res(0,INF);
        un mid=(l+r)>>1;
        if(ql<=mid)res=merge(res,Query(ql,qr,l,mid,num<<1));
        if(qr>mid)res=merge(res,Query(ql,qr,mid+1,r,num<<1|1));
        return res;
    }
}sgt[51];
std::vector<pll>g[MAXN];
int ctrb[MAXN][51];
//std::vector<pil>ctrb[MAXN];
int fa[MAXN],top[MAXN],loc[MAXN];
int dis[MAXN];
int cur=0;
string s;
void push(int u,int sp,int c,int d)
{
    if(s[u]=='1')sgt[c].modify(u,dis[d]);
    ctrb[u][c]=d;
    //ctrb[u].push_back(pil(c,d));
    //printf("sgt[%d] modify %d %lld\n",c,u,d);
    for(auto P:g[u])
    {
        int v=P.first;
        if(v!=sp&&v!=fa[u])push(v,sp,c,d);
    }
}
void dfs(int u,int t,bool type)
{
    //printf("u=%d,t=%d\n",u,t);
    if(type)++cur,t=u;
    top[u]=t,loc[u]=cur;
    //printf("loc[%d]=%d\n",u,cur);
    int p=u;
    while(p)
    {
        ctrb[u][loc[p]]=p;
        //ctrb[u].emplace_back(pil(loc[p],dis[p]));
        //printf("sgt[%d] modify %d %lld\n",loc[p],u,dis[p]);
        if(s[u]=='1')sgt[loc[p]].modify(u,dis[p]);
        p=fa[top[p]];
    }
    //printf("now,u=%d\n",u);
    bool flag=0;
    for(auto P:g[u])
    {
        int v=P.first;
        ll w=P.second;
        if(v==fa[u])continue;
        fa[v]=u,dis[v]=dis[u]+w;
        dfs(v,t,flag);
        flag=1;
    }
    flag=0;
    for(auto P:g[u])
    {
        int v=P.first;
        if(v==fa[u])continue;
        if(flag)push(u,v,cur,u);
        flag=1;
    }
}

int main()
{
    memset(ctrb,-1,sizeof ctrb);
    //freopen("K.in","r",stdin);
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>q>>s;
    s.insert(s.begin(),0);
    for(int i=1;i<n;++i)
    {
        int u,v,w;
        cin>>u>>v>>w;
        g[u].emplace_back(pll(v,w));
        g[v].emplace_back(pll(u,w));
    }
    //for(int i=1;i<=n;++i)val[0][i]=-1;
    for(int k=1;k<=50;++k)sgt[k].build();
    dfs(1,1,1);
    //puts("Pass dfs!");
    while(q--)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            int x;
            cin>>x;
            if(s[x]=='1')
            {
                for(int c=1;c<=cur;++c)
                    sgt[c].modify(x,-1);
                s[x]='0';
            }
            else
            {
                for(int c=1;c<=cur;++c)
                    if(ctrb[x][c]!=-1)
                        sgt[c].modify(x,dis[ctrb[x][c]]);
                s[x]='1';
            }
        }
        else
        {
            int l,r;
            cin>>l>>r;
            ll ans=0;
            for(int k=1;k<=cur;++k)
            {
                pll f=sgt[k].Query(l,r);
                ans+=f.first-f.second;
            }
            if(ans<0)cout<<"-1\n";
            else cout<<(ans<<1)<<'\n';
        }
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 155236kb

input:

5 6
10110
1 2 1
1 3 10
2 4 100
3 5 1000
2 1 5
1 3
2 1 5
2 2 4
2 5 5
2 1 1

output:

222
202
0
-1
0

result:

ok 5 number(s): "222 202 0 -1 0"

Test #2:

score: -100
Wrong Answer
time: 102ms
memory: 153276kb

input:

50 200000
00100100100001101010110100000111100011101110011010
14 47 940241413
11 43 331483591
37 38 496247070
47 46 832459694
7 15 16479291
1 30 402388666
30 8 513064064
46 50 739311480
5 4 761894947
32 41 631669659
17 24 715786564
35 20 763151642
32 33 492466005
39 11 186023146
9 7 805081251
3 42 25...

output:

11787339038
-1
35291811098
50402776806
29375337842
41312555684
-1
26169248764
37510518668
34793858520
52243441218
-1
-1
42434961382
19175826676
-1
13119403830
-1
-1
-1
44684190768
34297560936
45737341932
29182101246
-1
-1
33046070860
-1
60919750548
-1
17366610184
52901670650
-1
-1
14729381762
-1
-1
...

result:

wrong answer 1st numbers differ - expected: '17149847378', found: '11787339038'