QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#429542#8133. When Anton Saw This Task He Reacted With 😩lmeowdnRE 0ms38220kbC++143.8kb2024-06-02 16:45:272024-06-02 16:45:29

Judging History

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

  • [2024-06-02 16:45:29]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:38220kb
  • [2024-06-02 16:45:27]
  • 提交

answer

//Shirasu Azusa 2024.6
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x)  {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x)  {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x)  {return (x==0?-1:__builtin_ctzll(x));}

#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;  
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
  int x=0,w=1; char c=getchar(); 
  while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
  while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();} 
  return x*w;
}

const int N=2e5+5,mod=998244353;
struct Vec {
  int a[3];
  Vec(int x=0) {rep(i,0,2) a[i]=x;}
};
struct Mat {
  int a[3][3];
  Mat(int x=0) {
    memset(a,0,sizeof(a));
    a[0][0]=a[1][1]=a[2][2]=x;
  }
  Mat(Vec x,int t) {
    rep(i,0,2) a[(i+2)%3][(i+1)%3]=t*x.a[i];
    rep(i,0,2) a[(i+1)%3][(i+2)%3]=-t*x.a[i];
    rep(i,0,2) a[i][i]=0;
  }
};
Mat operator * (const Mat &x,const Mat &y) {
  Mat z;
  rep(i,0,2) rep(j,0,2) rep(k,0,2)
    z.a[i][k]=(z.a[i][k]+x.a[i][j]*y.a[j][k])%mod;
  return z;
}
Vec operator * (const Vec &x,const Mat &y) {
  Vec z;
  rep(i,0,2) rep(j,0,2)
    z.a[j]=(z.a[j]+x.a[i]*y.a[i][j])%mod;
  return z;
}

int n,q,pos[N],id[N],top[N],sz[N],son[N],fa[N],tick,l[N],r[N],w[N];
Vec a[N]; vi e[N];

namespace SegT {
  #define ls ((p)<<1)
  #define rs ((p)<<1|1)
  pair<Vec,Mat> f[N];
  auto operator + (pair<Vec,Mat> a,pair<Vec,Mat> b) {
    return mp(a.fi*b.se,a.se*b.se);
  }
  void build(int p,int l,int r) {
    if(l==r) {f[p].fi=a[id[l]],f[p].se=Mat(a[id[l]],w[id[l]]); return;}
    int mid=l+r>>1; build(ls,l,mid), build(rs,mid+1,r);
    f[p]=f[ls]+f[rs];
  }
  void mdf(int p,int l,int r,int x) {
    if(l==r) {f[p].fi=a[id[l]],f[p].se=Mat(a[id[l]],w[id[l]]); return;}
    int mid=l+r>>1; x<=mid?mdf(ls,l,mid,x):mdf(rs,mid+1,r,x);
    f[p]=f[ls]+f[rs];
  }
  auto qry(int p,int l,int r,int x,int y) {
    if(l==x&&r==y) return f[p]; int mid=l+r>>1;
    if(y<=mid) return qry(ls,l,mid,x,y);
    else if(x>mid) return qry(rs,mid+1,r,x,y);
    else return qry(ls,l,mid,x,mid)+qry(rs,mid+1,r,mid+1,y);
  }
}

void dfs1(int u) {
  for(int v:e[u]) {
    dfs1(v); fa[v]=u;
    if(sz[v]>sz[son[u]]) son[u]=v; sz[u]+=sz[v];
  } sz[u]++;
}
void dfs2(int u,int tp) {
  top[u]=tp;
  if(!e[u].size()) {
    ++tick; id[tick]=u; pos[u]=tick;
    chmin(l[tp],tick), chmax(r[tp],tick);
  } else {
    dfs2(son[u],tp);
    for(int v:e[u]) if(v!=son[u]) {
      ++tick; id[tick]=v; pos[v]=tick;
      chmin(l[tp],tick), chmax(r[tp],tick);
    }
    for(int v:e[u]) if(v!=son[u]) {
      if(e[v].size()) dfs2(v,v);
    }
  }
}
Vec mdf(int u,Vec t) {
  for(;u!=1;) {
    a[u]=t; SegT::mdf(1,1,n,pos[u]);
    u=top[fa[u]]; t=SegT::qry(1,1,n,l[u],r[u]).fi;
  }
  return t;
}

signed main() {
  n=read(), q=read();
  rep(i,1,n) l[i]=N;
  rep(i,1,n) {
    static char op[4]; scanf("%s",op);
    if(op[0]=='x') {
      rep(j,0,1) e[i].eb(read());
      w[e[i][0]]=-1, w[e[i][1]]=1;
    } else {
      rep(j,0,2) a[i].a[j]=read();
    }
  }
  dfs1(1); dfs2(1,1);
  SegT::build(1,1,n);
  rep(i,1,q) {
    int u=read(); Vec t; rep(j,0,2) t.a[j]=read();
    t=mdf(u,t); printf("%lld %lld %lld\n",t.a[0],t.a[1],t.a[2]);
  }
  return 0;
}

詳細信息

Test #1:

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

input:

5 3
x 2 3
v 1 0 1
x 4 5
v 0 2 1
v 1 1 1
4 1 2 3
5 0 1 1
4 0 2 2

output:

-2 0 2
1 -2 -1
0 0 0

result:

ok 9 numbers

Test #2:

score: -100
Runtime Error

input:

199999 100000
x 137025 65661
v 572518668 158967010 74946561
x 129836 192657
x 141948 187810
v 574918069 328924434 141474729
x 143312 111002
x 52772 148497
v 922857701 690080961 651915759
v 656198340 28002884 129579416
v 639893144 265359784 646791226
v 796871409 411409966 598676495
v 882562617 224394...

output:


result: