QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#310773 | #6404. Shuttle Tour | PlentyOfPenalty | ML | 0ms | 153152kb | C++17 | 3.9kb | 2024-01-21 17:35:18 | 2024-01-21 17:35:19 |
Judging History
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)
{
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]];
}
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);
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);
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: 153152kb
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
Memory Limit Exceeded
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...