QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#803111#9862. Antivirusucup-team3586#WA 79ms36356kbC++236.7kb2024-12-07 16:02:572024-12-07 16:02:59

Judging History

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

  • [2024-12-07 16:02:59]
  • 评测
  • 测评结果：WA
  • 用时：79ms
  • 内存：36356kb
查看
  • [2024-12-07 16:02:57]
  • 提交

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
namespace domtree
{
	constexpr int MAX = 3e5 + 5;
	constexpr int INF = 0x5ffffff;

	struct E {
	int v, x;
	} e[MAX * 4];

	int n, m, u, v, tot, dfc;
	int ans[MAX], dfn[MAX], pos[MAX], sdm[MAX], idm[MAX], fa[MAX], mn[MAX],
		fth[MAX];
	int h[3][MAX * 2];

	void add(int x, int u, int v) {
	e[++tot] = {v, h[x][u]};
	h[x][u] = tot;
	}

	void dfs(int u) {
	dfn[u] = ++dfc;
	pos[dfc] = u;
	for (int i = h[0][u]; i; i = e[i].x) {
		int v = e[i].v;
		if (!dfn[v]) {
		dfs(v);
		fth[v] = u;
		}
	}
	}

	int find(int x) {
	if (fa[x] == x) {
		return x;
	}
	int tmp = fa[x];
	fa[x] = find(fa[x]);
	if (dfn[sdm[mn[tmp]]] < dfn[sdm[mn[x]]]) {
		mn[x] = mn[tmp];
	}
	return fa[x];
	}

	void tar(int st) {
	dfs(st);
	for (int i = 1; i <= n; ++i) {
		mn[i] = fa[i] = sdm[i] = i;
	}
	for (int i = dfc; i >= 2; --i) {
		int u = pos[i], res = INF;
		for (int j = h[1][u]; j; j = e[j].x) {
		int v = e[j].v;
		if (!dfn[v]) {
			continue;
		}
		find(v);
		if (dfn[v] < dfn[u]) {
			res = std::min(res, dfn[v]);
		} else {
			res = std::min(res, dfn[sdm[mn[v]]]);
		}
		}
		sdm[u] = pos[res];
		fa[u] = fth[u];
		add(2, sdm[u], u);
		u = fth[u];
		for (int j = h[2][u]; j; j = e[j].x) {
		int v = e[j].v;
		find(v);
		if (u == sdm[mn[v]]) {
			idm[v] = u;
		} else {
			idm[v] = mn[v];
		}
		}
		h[2][u] = 0;
	}
	for (int i = 2; i <= dfc; ++i) {
		int u = pos[i];
		if (idm[u] != sdm[u]) {
		idm[u] = idm[idm[u]];
		}
	}
	for (int i = dfc; i >= 2; --i) {
		++ans[pos[i]];
		ans[idm[pos[i]]] += ans[pos[i]];
	}
	++ans[1];
	}

	void domtree(int _n,int _m,vector<pii> E)
	{
		tot=dfc=0;
		n=_n;
		m=_m;
		u=v=0;
		for(int i=0;i<=n+10;i++)
		{
			ans[i]=dfn[i]=pos[i]=0;
			mn[i]=idm[i]=sdm[i]=0;
			fa[i]=fth[i]=0;
		}
		for(int i=0;i<3;i++)
			for(int j=0;j<=n+n+10;j++)
				h[i][j]=0;
		for(auto pr:E)
		{
			add(0,pr.first,pr.second);
			add(1,pr.second,pr.first);
		}
		tar(1);
	}
}
ll c[100100];
int p[100100];
vector<int> G[100100];
ll ans[100100];
int siz[100100],son[100100],tp[100100],dfn[100100],ind[100100],tot;
void dfs1(int u)
{
	siz[u]=1;
	son[u]=0;
	tp[u]=0;
	for(auto v:G[u])
	{
		dfs1(v);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])
			son[u]=v;
	}
}
void dfs2(int u)
{
	if(!tp[u]) tp[u]=u;
	tot++;
	dfn[u]=tot;
	ind[tot]=u;
	if(son[u])
	{
		tp[son[u]]=tp[u];
		dfs2(son[u]);
	}
	for(auto v:G[u])
		if(v!=son[u])
			dfs2(v);
}
namespace segt
{
	#define ls (x<<1)
	#define rs (ls|1)
	ll c[100100<<2];
	ll mn1[100100<<2],mn2[100100<<2];
	ll mx[100100<<2],smx[100100<<2];
	ll add[100100<<2],addmx[100100<<2];
	void build(int x,int l,int r)
	{
		mx[x]=0;
		smx[x]=-1ll*inf*inf;
		mn1[x]=c[x];
		mn2[x]=1ll*inf*inf;
		add[x]=addmx[x]=0;
		if(l==r) return ;
		int mid=(l+r)/2;
		build(ls,l,mid);
		build(rs,mid+1,r);
	}
	void modify(int x,int l,int r,int p,ll vc)
	{
		if(l==r)
		{
			c[x]=vc;
			return ;
		}
		int mid=(l+r)/2;
		if(p<=mid) modify(ls,l,mid,p,vc);
		else modify(rs,mid+1,r,p,vc);
		c[x]=min(c[ls],c[rs]);
	}
	void pushdown(int x,int l,int r)
	{
		mx[x]+=add[x];
		smx[x]+=add[x];
		mx[x]+=addmx[x];
		mn1[x]+=add[x]+addmx[x];
		mn2[x]+=add[x];
		if(l!=r)
		{
			add[ls]+=add[x];
			add[rs]+=add[x];
			addmx[ls]+=addmx[x];
			addmx[rs]+=addmx[x];
		}
		add[x]=0;
		addmx[x]=0;
	}
	void pushup(int x,int l,int r)
	{
		int mid=(l+r)/2;
		pushdown(ls,l,mid);
		pushdown(rs,mid+1,r);
		mx[x]=max(mx[ls],mx[rs]);
		smx[x]=max(smx[ls],smx[rs]);
		mn1[x]=1ll*inf*inf;
		mn2[x]=min(mn2[ls],mn2[rs]);
		if(mx[ls]!=mx[x])
		{
			smx[x]=max(smx[x],mx[ls]);
			mn2[x]=min(mn2[x],mn1[ls]);
		}
		else
			mn1[x]=min(mn1[x],mn1[ls]);
		if(mx[rs]!=mx[x])
		{
			smx[x]=max(smx[x],mx[rs]);
			mn2[x]=min(mn2[x],mn1[rs]);
		}
		else
			mn1[x]=min(mn1[x],mn1[rs]);
	}
	void range_add(int x,int l,int r,int ql,int qr,ll v)
	{
		pushdown(x,l,r);
		if(ql<=l&&r<=qr)
		{
			add[x]+=v;
			return ;
		}
		int mid=(l+r)/2;
		if(ql<=mid) range_add(ls,l,mid,ql,qr,v);
		if(qr>mid) range_add(rs,mid+1,r,ql,qr,v);
		pushup(x,l,r);
	}
	void update(int x,int l,int r,int ql,int qr,ll v)
	{
		pushdown(x,l,r);
		if(v>=mx[x]) return ;
		if(ql<=l&&r<=qr)
		{
			if(v>=smx[x])
			{
				addmx[x]+=v-mx[x];
				return ;
			}
			else
			{
				int mid=(l+r)/2;
				update(ls,l,mid,ql,qr,v);
				update(rs,mid+1,r,ql,qr,v);
				pushup(x,l,r);
				return ;
			}
		}
		int mid=(l+r)/2;
		if(ql<=mid) update(ls,l,mid,ql,qr,v);
		if(qr>mid) update(rs,mid+1,r,ql,qr,v);
		pushup(x,l,r);
	}
	ll query(int x,int l,int r,int ql,int qr)
	{
		pushdown(x,l,r);
		if(l==ql&&r==qr) return min(mn1[x],mn2[x]);
		int mid=(l+r)/2;
		if(qr<=mid) return query(ls,l,mid,ql,qr);
		if(ql>mid) return query(rs,mid+1,r,ql,qr);
		return min(query(ls,l,mid,ql,mid),query(rs,mid+1,r,mid+1,qr));
	}
	#undef ls
	#undef rs
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		int n,m,q;
		cin>>n>>m>>q;
		vector<pii> E;
		for(int i=1;i<=m;i++)
		{
			int u,v;
			cin>>u>>v;
			E.pb(v,u);
		}
		domtree::domtree(n,m,E);
		for(int i=1;i<=n;i++)
			cin>>c[i];
		for(int i=1;i<=n;i++)
			G[i].clear();
		for(int i=2;i<=n;i++)
		{
			p[i]=domtree::idm[i];
			G[p[i]].pb(i);
		}
		tot=0;
		dfs1(1);
		dfs2(1);
		for(int i=1;i<=n;i++)
			segt::modify(1,1,n,dfn[i],c[i]);
		segt::build(1,1,n);
		for(int i=1;i<=q;i++)
		{
			int u;
			ll cost;
			cin>>u>>cost;
			ans[i]=ans[i-1]+cost;
			int tmp=u;
			vector<pii> vec;
			while(tmp)
			{
				int L=dfn[tp[tmp]];
				int R=dfn[tmp];
				vec.pb(L,R);
				tmp=p[tp[tmp]];
			}
			srt(vec);
			for(auto pr:vec)
				ans[i]=min(ans[i],segt::query(1,1,n,pr.first,pr.second));
			int cur=1;
			for(auto pr:vec)
			{
				if(cur<pr.first)
				{
					segt::range_add(1,1,n,cur,pr.first-1,cost);
					segt::update(1,1,n,cur,pr.first-1,ans[i]);
				}
				cur=pr.second+1;
			}
			if(cur<=n)
			{
				segt::range_add(1,1,n,cur,n,cost);
				segt::update(1,1,n,cur,n,ans[i]);
			}
			cout<<ans[i]<<" ";
		}
		cout<<'\n';
	}
	return 0;
}
源文件, 语言: C++23

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 36356kb

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 202 
10

result:

ok 9 numbers

Test #2:

score: -100
Wrong Answer
time: 79ms
memory: 34628kb

input:

10000
10 15 10
5 4
4 8
8 1
9 1
3 1
7 10
2 4
2 8
10 9
8 1
3 2
8 9
6 3
9 6
9 7
109573034 995191779 629441974 818963404 427826881 504492389 571193150 526828914 397022133 261597684
10 372333138
2 502585557
6 146333017
6 522319681
10 272972971
9 958277860
6 81039902
10 30321248
6 459502525
6 753468360
10...

output:

109573034 109573034 109573034 109573034 109573034 109573034 109573034 109573034 109573034 109573034 
302793882 302793882 302793882 302793882 392542446 392542446 392542446 392542446 392542446 392542446 
14673922 527692254 527692254 527692254 527692254 527692254 527692254 527692254 527692254 527692254...

result:

wrong answer 243rd numbers differ - expected: '534427025', found: '481877342'
English 繁體中文 简体中文

服务器时间: 2025-01-21 04:45:09 | 开源项目