QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#187776 | #6404. Shuttle Tour | UESTC_Guest_WiFi | RE | 0ms | 8432kb | C++20 | 4.1kb | 2023-09-24 22:11:19 | 2023-09-24 22:11:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5;
int n,q;
char s[N+5];
struct E{
int v,w;
E(int v=0,int w=0):v(v),w(w){}
};
vector<E> e[N+5];
int fa[N+5],dep[N+5];
ll dw[N+5];
int sz[N+5],son[N+5],top[N+5];
int dfn[N+5],dfns;
int tot,bl[N+5];
void dfs1(int u,int tf){
dfn[u]=++dfns;
fa[u]=tf; sz[u]=1;
dep[u]=dep[tf]+1;
for(auto it:e[u]){
int v=it.v;
if(v==tf) continue;
dw[v]=dw[u]+it.w;
dfs1(v,u);
if(sz[v]>sz[son[u]]) son[u]=v;
sz[u]+=sz[v];
}
}
void dfs2(int u,int tf){
top[u]=tf;
if(!son[u]) return;
dfs2(son[u],tf);
for(auto it:e[u]){
int v=it.v;
if(v!=son[u]&&v!=fa[u])
dfs2(v,v);
}
}
int LCA(int u,int v){
if(!u||!v) return u+v;
// printf("%d %d\n",u,v);
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) swap(u,v);
u=fa[top[u]];
}
return dep[u]<dep[v]?u:v;
}
namespace Segtr{
#define lc id<<1
#define rc id<<1|1
int mx[N*4+5][55],lca[N*4+5];
int cmp(int x,int y){ return !x||!y?x+y:dep[x]<dep[y]?y:x; }
void push_up(int id){
// printf("%d %d ",lca[lc],lca[rc]);
lca[id]=LCA(lca[lc],lca[rc]);
// printf("%d\n",lca[id]);
for(int i=1;i<=tot;i++)
mx[id][i]=cmp(mx[lc][i],mx[rc][i]);
}
void build(int l,int r,int id){
if(l==r){
if(s[l]) lca[id]=mx[id][bl[l]]=l;
return;
}
int mid=l+r>>1;
build(l,mid,lc); build(mid+1,r,rc);
push_up(id);
}
void upd(int l,int r,int p,int id){
if(l==r){
s[l]^=1;
if(s[l]) lca[id]=mx[id][bl[l]]=l;
else lca[id]=mx[id][bl[l]]=0;
return;
}
int mid=l+r>>1;
if(p<=mid) upd(l,mid,p,lc);
else upd(mid+1,r,p,rc);
push_up(id);
}
int res[55];
void update(int val[],int vlca){
res[0]=LCA(res[0],vlca);
for(int i=1;i<=tot;i++)
res[i]=cmp(res[i],val[i]);
}
void query(int l,int r,int st,int en,int id){
if(st<=l&&en>=r){
// printf("%d %d\n",l,r);
update(mx[id],lca[id]); return;
}
int mid=l+r>>1;
if(st<=mid) query(l,mid,st,en,lc);
if(en>mid) query(mid+1,r,st,en,rc);
}
}
using namespace Segtr;
bool used[N+5];
void prep(){
dfs1(1,0); dfs2(1,1);
for(int i=2;i<=n;i++)
if(e[i].size()==1){
tot++;
for(int j=i;j&&!used[j];j=fa[j]){
bl[j]=tot; used[j]=1;
}
}
build(1,n,1);
}
bool cmpv(int x,int y){ return dfn[x]<dfn[y]?x:y; }
ll calc(vector<int> ver){
if(!ver.size()) return -1;
sort(ver.begin(),ver.end(),cmpv);
static int st[105];
int s=0; ll ans=0;
st[++s]=ver[0];
for(int i=1;i<ver.size();i++){
int u=ver[i],lca=LCA(u,st[s]);
// printf("%d\n",lca);
// printf("%d ",u);
while(s>1&&dep[st[s-1]]>dep[lca]){
ans+=dw[st[s]]-dw[st[s-1]];
s--;
}
if(dep[st[s]]>dep[lca]){
ans+=dw[st[s]]-dw[lca];
s--;
}
assert(s>=0);
if(st[s]!=lca) st[++s]=lca;
st[++s]=u;
}
// puts("");
while(s>1){
ans+=dw[st[s]]-dw[st[s-1]];
s--;
}
return ans<<1;
}
int main(){
scanf("%d %d",&n,&q);
scanf("%s",s+1);
for(int i=1;i<=n;i++) s[i]-='0';
for(int i=1,u,v,w;i<n;i++){
scanf("%d %d %d",&u,&v,&w);
e[u].push_back(E(v,w));
e[v].push_back(E(u,w));
}
prep();
while(q--){
int tp,l,r;
scanf("%d %d",&tp,&l);
if(tp==1) upd(1,n,l,1);
else{
scanf("%d",&r);
memset(res,0,sizeof res);
query(1,n,l,r,1);
vector<int> ver;
for(int i=0;i<=tot;i++)
if(res[i]) ver.push_back(res[i]);
printf("%lld\n",calc(ver));
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 8432kb
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
Runtime Error
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:
24506085044 -1 38355005062 48798384492 31459899764 41975722220 13389107768 26942391944 29021962572 28891339284 46277001756 11089007554 9380710234 36638557126 21202517698 2856655228 17025146454 0 -1 10440149760 39507147242 29639654552 36625007326 27484870712 8533875940 7695830712 31035276400 0 473533...