QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#787037#6404. Shuttle TourASnownWA 199ms562792kbC++174.0kb2024-11-27 08:58:412024-11-27 08:58:41

Judging History

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

  • [2024-11-27 08:58:41]
  • 评测
  • 测评结果:WA
  • 用时:199ms
  • 内存:562792kb
  • [2024-11-27 08:58:41]
  • 提交

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'