QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #803133 | #9862. Antivirus | ucup-team3161# | WA | 3ms | 83692kb | C++14 | 8.4kb | 2024-12-07 16:08:23 | 2024-12-07 16:08:24 |
Judging History
answer
// what is matter? never mind.
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
//#define ll __int128
//#define ull unsigned long long
#define int long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f?-x:x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 500005
#define inf 0x3f3f3f3f3f3f3f3f
int n,m;
vi e[maxn];
namespace TT{
vi e[maxn],g[maxn],dom[maxn];
int fa[maxn],dfn[maxn],que[maxn],idx;
void adde(int u,int v){e[u].pb(v);}
void dfs(int u){
que[dfn[u]=++idx]=u;
for(int v:e[u]){
if(!dfn[v])dfs(v),fa[dfn[v]]=dfn[u];
g[dfn[v]].pb(dfn[u]);
}
}
int p[maxn],mn[maxn],sdom[maxn],idom[maxn];
int get(int u){
if(p[u]!=p[p[u]]){
if(sdom[mn[u]]>sdom[get(p[u])])mn[u]=get(p[u]);
p[u]=p[p[u]];
}return mn[u];
}
void solve()
{
// cout<<"solve"<<endl;
For(i,1,n)p[i]=mn[i]=sdom[i]=i;
dfs(1);
Rep(i,n,2){
for(int j:g[i])sdom[i]=min(sdom[i],sdom[get(j)]);
dom[sdom[i]].pb(i);
int x=p[i]=fa[i];
for(int j:dom[x])idom[j]=(sdom[get(j)]<x?get(j):x);
dom[x].clear();
}
For(i,2,n){
if(idom[i]!=sdom[i])idom[i]=idom[idom[i]];
// cout<<"ADD "<<que[idom[i]]<<' '<<que[i]<<endl;
::e[que[idom[i]]].pb(que[i]);
}
// cout<<"qwq"<<endl;
}
void init(){
For(i,1,n) e[i].clear(),g[i].clear(),dom[i].clear(),fa[i]=dfn[i]=que[i]=p[i]=mn[i]=sdom[i]=idom[i]=0; idx=0;
For(i,1,m){
int u=read(),v=read();
// cout<<"edge "<<u<<" "<<v<<endl;
e[v].pb(u);
}
solve();
}
}
int fa[maxn],son[maxn],sz[maxn],dep[maxn];
int dfn[maxn],out[maxn],top[maxn],que[maxn],idx;
void dfs1(int u){
sz[u]=1;
for(auto v:e[u]){
if(v==fa[u])continue;
fa[v]=u,dep[v]=dep[u]+1,dfs1(v),sz[u]+=sz[v];
if(sz[v]>sz[son[u]])son[u]=v;
}
}
void dfs2(int u,int tp){
top[u]=tp,dfn[u]=++idx,que[idx]=u;
if(son[u])dfs2(son[u],tp);
for(auto v:e[u])if(v!=fa[u]&&v!=son[u])dfs2(v,v);
out[u]=idx;
}
int lca(int u,int v){
for(;top[u]!=top[v];u=fa[top[u]])if(dep[top[u]]<dep[top[v]])swap(u,v);
return dep[u]<dep[v]?u:v;
}
int kth(int u,int k){
while(k>=dfn[u]-dfn[top[u]]+1&&dfn[u]!=1)
k-=dfn[u]-dfn[top[u]]+1,u=fa[top[u]];
return que[dfn[u]-k];
}
int jump(int u,int v){
for(;top[u]!=top[v];u=fa[top[u]])
if(fa[top[u]]==v)return top[u];
return son[v];
}
/*
weihu g[i]=f[i]-c[i]
qmin g[i]+c[i]
g[i]=min(g[i],X)
g[i] range add
*/
struct info{
int mx,cmx;
int mx2,cmx2;
info (){
mx=-inf;cmx=inf;
mx2=-inf;cmx2=inf;
}
};
struct oper{
int add,addmx;
oper (){
add=addmx=0;
}
};
info operator +(info a,info b){
info c;
c.mx=max(a.mx,b.mx);
c.mx2=max((a.mx==c.mx?a.mx2:a.mx),(b.mx==c.mx?b.mx2:b.mx));
c.cmx2=min((a.mx==c.mx?a.cmx2:min(a.cmx,a.cmx2)),(b.mx==c.mx?b.cmx2:min(b.cmx,b.cmx2)));
c.cmx=inf;
if(a.mx==c.mx) c.cmx=min(c.cmx,a.cmx);
if(b.mx==c.mx) c.cmx=min(c.cmx,b.cmx);
return c;
}
void app(oper &a,oper b,bool is){
a.add+=b.add;
if(is) a.addmx+=b.addmx;
}
void app(info &a,oper b,bool is){
if(is){
a.mx+=b.add+b.addmx;
a.cmx+=b.add+b.addmx;
}else{
a.mx+=b.add;
a.cmx+=b.add;
}
a.mx2+=b.add;
a.cmx2+=b.add;
}
template<class info,class oper>
struct segt{
int n;
vector<info>tr;
vector<oper>tag;
void init(vector<info>a){
n=a.size(); assert(n);
tr.assign(4<<__lg(n),info());
tag.assign(4<<__lg(n),oper());
function<void(int,int,int)>build=[&](int p,int l,int r){
if(l==r)return tr[p]=a[l],void();
int mid=l+r>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r),up(p);
};
build(1,0,n-1);
}
void init(int _n){
n=_n; assert(n);
tr.assign(4<<__lg(n),info());
tag.assign(4<<__lg(n),oper());
}
void up(int p){
tr[p]=tr[p<<1]+tr[p<<1|1];
}
void pt(int p,oper v){
app(tag[p],v,1);
app(tr[p],v,1);
//tr[p]+=v;
}
void down(int p){
bool b1=(tr[p<<1].mx>=tr[p<<1|1].mx);
bool b2=(tr[p<<1].mx<=tr[p<<1|1].mx);
app(tag[p<<1],tag[p],b1);
app(tr[p<<1],tag[p],b1);
app(tag[p<<1|1],tag[p],b2);
app(tr[p<<1|1],tag[p],b2);
tag[p]=oper();
// auto tt=tr[p<<1]+tr[p<<1|1];
// if(tt.cmx!=tr[p].cmx || tt.cmx2!=tr[p].cmx2){
// cout<<"???\n";
//
// }
}
void upd(int p,int l,int r,int x,info y){
if(l==r)return tr[p]=y,void();
int mid=l+r>>1; down(p);
if(x<=mid)upd(p<<1,l,mid,x,y);
else upd(p<<1|1,mid+1,r,x,y); up(p);
}
// beats
void mdf(int p,int l,int r,int ql,int qr,int v){
// cout<<"mdf "<<p<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<" "<<v<<endl;
// cout<<"mx,mx2 "<<tr[p].mx<<" "<<tr[p].mx2<<endl;
// cout<<"cmx,cmx2 "<<tr[p].cmx<<" "<<tr[p].cmx2<<endl;
if(v>=tr[p].mx) return;
if(l>=ql&&r<=qr && v>tr[p].mx2) {
oper tmp;
// cout<<"L,r "<<l<<" "<<r<<"\n";
// cout<<"apply "<<v<<" "<<tr[p].mx<<"\n";
tmp.addmx=v-tr[p].mx;
return pt(p,tmp);
}
int mid=l+r>>1; down(p);
if(ql<=mid)mdf(p<<1,l,mid,ql,qr,v);
if(qr>mid)mdf(p<<1|1,mid+1,r,ql,qr,v); up(p);
}
void mdf(int p,int l,int r,int ql,int qr,oper v){
if(l>=ql&&r<=qr)return pt(p,v);
int mid=l+r>>1; down(p);
if(ql<=mid)mdf(p<<1,l,mid,ql,qr,v);
if(qr>mid)mdf(p<<1|1,mid+1,r,ql,qr,v); up(p);
}
info ask(int p,int l,int r,int ql,int qr){
if(l>=ql&&r<=qr)return tr[p];
int mid=l+r>>1; down(p);
if(qr<=mid)return ask(p<<1,l,mid,ql,qr);
if(ql>mid)return ask(p<<1|1,mid+1,r,ql,qr);
return ask(p<<1,l,mid,ql,qr)+ask(p<<1|1,mid+1,r,ql,qr);
}
void dfs(int p,int l,int r){
// cout<<"TR l,r "<<l<<" "<<r<<" "<<"\n";
// cout<<tr[p].cmx<<" " <<tr[p].cmx2<<"\n";
if(l==r)return;
int mid=l+r>>1; down(p);
dfs(p<<1,l,mid);
dfs(p<<1|1,mid+1,r);
}
void upd(int x,info y){
--x;
upd(1,0,n-1,x,y);
}
void mdf(int l,int r,oper y){
if(l>r)return;
// cout<<"MDF "<<l<<" "<<r<<" "<<y.add<<endl;
--l,--r;
mdf(1,0,n-1,l,r,y);
}
info ask(int l,int r){
if(l>r)return info();
--l,--r;
return ask(1,0,n-1,l,r);
}
};
segt<info,oper> T;
int res[maxn];
int b[maxn],c[maxn],sumb[maxn],a[maxn],q;
/*
weihu g[i]=f[i]-c[i]
qmin g[i]+c[i]
g[i]=min(g[i],X)
g[i] range add
*/
void work()
{
n=read(),m=read(),q=read();
For(i,1,n) e[i].clear(),dfn[i]=fa[i]=top[i]=0; idx=0;
TT::init();
// For(i,1,n) for(int v:e[i]) cout<<"tree "<<i<<" "<<v<<endl;
dfs1(1),dfs2(1,1);
For(i,1,n)c[i]=read();
For(i,1,q){
a[i]=read(),b[i]=read();
sumb[i]=sumb[i-1]+b[i];
}
vector<info>mys;
For(i,1,n) {
int u=que[i];
info t;
t.mx=0;
t.cmx=c[u];
mys.pb(t);
}
T.init(mys);
For(i,1,q+1){
int mns=sumb[i-1];
mns=min(mns,T.tr[1].cmx);
mns=min(mns,T.tr[1].cmx2);
// cout<<"T1: cmx,cmx2: "<<T.tr[1].cmx<<" "<<T.tr[1].cmx2<<"\n";
res[i-1]=mns;
// cout<<"solve "<<i<<" "<<mns<<endl;
if(i==q+1) break;
T.mdf(1,0,n-1,0,n-1,mns);
// For(j,1,n){
// auto t=T.ask(j,j);
// // cout<<"j: "<<j<<"\n";
// // cout<<"mx,cmx "<<t.mx<<" "<<t.cmx<<"\n";
// }
oper ad; ad.add=c[i];
T.mdf(1,n,ad);
ad.add=-c[i];
int u=a[i];
while(u){
int t=top[u];
T.mdf(dfn[t],dfn[u],ad);
u=fa[top[u]];
}
// For(j,1,n){
// auto t=T.ask(j,j);
// cout<<"j: "<<j<<"\n";
// cout<<"mx,cmx "<<t.mx<<" "<<t.cmx<<"\n";
// }
T.dfs(1,0,n-1);
}
For(i,1,q){
printf("%lld ",res[i]);
}puts("");
}
signed main()
{
//freopen("my.out","w",stdout);
int T=read();
while(T--)work();
return 0;
}
/*
1
7 6 4
2 1
3 1
4 2
5 2
6 3
7 3
4 3 5 2 2 1 1
4 2
5 2
6 2
7 2
(4 3 2 2 5 1 1)
0 0 0 0 0 0 0
0 0 0 4 4 4 4
*/
详细
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 83692kb
input:
3 7 6 4 2 1 3 1 4 2 5 2 6 3 7 3 4 3 5 2 2 1 1 4 2 5 2 6 2 7 2 5 6 4 1 3 3 2 2 1 4 2 5 4 2 5 10000 10000 2 100 5 5 1000 4 1000 3 1000 4 1000 4 4 1 2 1 3 1 4 2 4 3 100 1 1 100 4 10
output:
2 3 4 4 5 100 102 102 10
result:
wrong answer 8th numbers differ - expected: '202', found: '102'