QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#787037 | #6404. Shuttle Tour | ASnown | WA | 199ms | 562792kb | C++17 | 4.0kb | 2024-11-27 08:58:41 | 2024-11-27 08:58:41 |
Judging History
answer
#include<bits/stdc++.h>
#define file(F) freopen(#F".in","r",stdin),freopen(#F".out","w",stdout)
#define lowbit(x) ((x)&-(x))
#define ALL(x) (x).begin(),(x).end()
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define popc(x) (__builtin_popcountll((x)))
#define abs(x) ((x)>=0?(x):-(x))
using namespace std;
using ll=long long;
using uint=uint32_t;
template<typename T>
inline bool Max(T &x,T y) { return std::less<T>()(x,y)&&(x=y,true); }
template<typename T>
inline bool Min(T &x,T y) { return std::less<T>()(y,x)&&(x=y,true); }
void Solve();
const int N = 2e5+25;
int n,Q;
bool lt[N];
vector<pair<int,int>> e[N];
ll dis[N];
int dfn[N],pos[N],dfx,ed[N];
vector<int> top; int tp[N];
int st[N][20];
void dfs(int u,int fa,int t) {
pos[dfn[u]=++dfx]=u;
if(u==t) top.emplace_back(t); tp[u]=top.size()-1;
st[dfn[u]][0]=fa;
int son=0; for(auto [v,w]:e[u]) if(v!=fa) {
dis[v]=dis[u]+w; dfs(son=v,u,t); break;
} ed[u]=dfx;
for(auto [v,w]:e[u]) if(v!=fa&&v!=son) {
dis[v]=dis[u]+w; dfs(v,u,v);
}
}
int LCA(int x,int y) {
if(x==y) return x;
if((x=dfn[x])>(y=dfn[y])) swap(x,y);
int l=__lg(y-x++);
return min(st[x][l],st[y-(1<<l)+1][l],
[](int a,int b){ return dfn[a]<dfn[b]; });
}
inline ll dist(int x,int y) { return dis[x]+dis[y]-2*dis[LCA(x,y)]; }
struct SGT {
#define mid ((L+R)>>1)
#define ls (u<<1)
#define rs (ls|1)
int mx[N<<2],mn[N<<2];
set<int> leaf[N];
void build(int u,int L,int R) {
mx[u]=0,mn[u]=N;
if(L==R) return void(leaf[L].clear());
build(ls,L,mid),build(rs,mid+1,R);
}
void insert(int u,int L,int R,int x,int k) {
if(L==R) {
leaf[L].insert(k);
mx[u]=*leaf[L].rbegin();
mn[u]=*leaf[L].begin();
return ;
}
if(x<=mid) insert(ls,L,mid,x,k);
else insert(rs,mid+1,R,x,k);
mx[u]=max(mx[ls],mx[rs]),mn[u]=min(mn[ls],mn[rs]);
}
void erase(int u,int L,int R,int x,int k) {
if(L==R) {
leaf[L].erase(k);
if(leaf[L].empty())
mx[u]=0,mn[u]=N;
else {
mx[u]=*leaf[L].rbegin();
mn[u]=*leaf[L].begin();
}
return ;
}
if(x<=mid) erase(ls,L,mid,x,k);
else erase(rs,mid+1,R,x,k);
mx[u]=max(mx[ls],mx[rs]),mn[u]=min(mn[ls],mn[rs]);
}
int querymx(int u,int L,int R,int l,int r) {
if(l<=L&&R<=r) return mx[u];
if(r<=mid) return querymx(ls,L,mid,l,r);
if(l> mid) return querymx(rs,mid+1,R,l,r);
return max(querymx(ls,L,mid,l,r),querymx(rs,mid+1,R,l,r));
}
int querymn(int u,int L,int R,int l,int r) {
if(l<=L&&R<=r) return mn[u];
if(r<=mid) return querymn(ls,L,mid,l,r);
if(l> mid) return querymn(rs,mid+1,R,l,r);
return min(querymn(ls,L,mid,l,r),querymn(rs,mid+1,R,l,r));
}
#undef mid
#undef ls
#undef rs
} t[55];
signed main() {
#ifndef ONLINE_JUDGE
#endif
cin.tie(nullptr)->sync_with_stdio(false);
Solve();
}
void Solve() {
cin>>n>>Q;
for(int i=1;i<=n;i++) {
char ch; cin>>ch;
lt[i]=ch=='1';
}
for(int i=1;i<n;i++) {
int u,v,w; cin>>u>>v>>w;
e[u].emplace_back(v,w);
e[v].emplace_back(u,w);
}
dfs(1,0,1);
for(int l=0;l<19;l++) for(int i=1;i+(1<<l+1)-1<=n;i++)
st[i][l]=min(st[i][l],st[i+(1<<l)][l],
[](int a,int b){ return dfn[a]<dfn[b]; });
for(int i=0;i<top.size();i++) t[i].build(1,1,n);
for(int i=1;i<=n;i++) if(lt[i]) t[tp[i]].insert(1,1,n,i,dfn[i]);
while(Q--) {
int op,x,y; cin>>op;
if(op==1) {
cin>>x;
if(lt[x]^=1) t[tp[x]].insert(1,1,n,x,dfn[x]);
else t[tp[x]].erase(1,1,n,x,dfn[x]);
} else {
cin>>x>>y;
int rt=0,ed=0;
ll ans=0;
for(int i=0;i<top.size();i++) {
int p=t[i].querymn(1,1,n,x,y);
int q=t[i].querymx(1,1,n,x,y);
if(p>q) continue; p=pos[p],q=pos[q];
ans+=dist(p,q);
if(ed) ans+=dist(ed,p); ed=q;
if(!rt) rt=p;
}
if(rt) printf("%lld\n",ans+dist(rt,ed));
else puts("-1");
}
}
}
详细
Test #1:
score: 100
Accepted
time: 56ms
memory: 552948kb
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: 199ms
memory: 562792kb
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:
41441190716 -1 61198292884 72711803842 42803578356 72864309230 24235680334 44227211268 54497625956 54321518902 79584738100 24223007290 17314657386 62253860602 35703464718 2856655228 36863281622 0 -1 18374096912 63250069624 51915154336 58083199572 51037901782 25263748874 21629990106 58231969826 0 817...
result:
wrong answer 1st numbers differ - expected: '17149847378', found: '41441190716'