제출 #879716

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
879716		vjudge1	Tourism (JOI23_tourism)	C++17	100 / 100	1420 ms	39248 KiB

tourism

#include<stdio.h>
#include<algorithm>
#include<string.h>
#define N 100009
#define LG 19
#define B 9
#define pr pair<int*,int> 
using namespace std;
inline char nc()
{
	static char buf[99999],*l,*r;
	return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
	char c=nc();for(;c<'0'||'9'<c;c=nc());
	for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
int n,m,q,h[N],e[N<<1],nxt[N<<1],dfn[N],now,st[LG][N*3],lg[N*3];
int dep[N],a[N],cnt[N*3],lft[N*3],rgt[N*3],l,r,rsz;
long long ss,sss,ans[N];pr rbk[N*3];
inline void dfs(int i,int f)
{
	dfn[i]=now;st[0][now++]=dep[i]=dep[f]+1;
	for(int j=h[i];j;j=nxt[j])if(e[j]^f)dfs(e[j],i),st[0][now++]=dep[i];
}
struct node
{
	int id,l,r;
	inline bool operator<(node kkk)const
		{return l>>B^kkk.l>>B?l<kkk.l:r>kkk.r;}
}b[N];
inline int qry(int l,int r)
{
	if(l>r)l^=r^=l^=r;
	int i=lg[r-l];
	return min(st[i][l],st[i][r-(1<<i)+1]);
}
main()
{
	read(n);read(m);read(q);
	for(int i=2;i<=n*3;++i)lg[i]=lg[i>>1]+1;
	for(int i=1,u,v;i<n;++i)
		read(u),read(v),--u,--v,
		e[i]=v,nxt[i]=h[u],h[u]=i,
		e[i+n]=u,nxt[i+n]=h[v],h[v]=i+n;
	dfs(0,0);
	for(int i=now-1;i>=0;--i)for(int j=1;j<LG;++j)
		if(i+(1<<j-1)>=now)st[j][i]=st[j-1][i];
		else st[j][i]=min(st[j-1][i],st[j-1][i+(1<<j-1)]);
	for(int i=0;i<m;++i)read(a[i]),a[i]=dfn[--a[i]];
	for(int i=0;i<q;++i)b[i].id=i,read(b[i].l),read(b[i].r),
		--b[i].l,--b[i].r;
	sort(b,b+q);
	for(int i=0;i<q;++i)
	{
		if(!i||(b[i].l>>B^b[i-1].l>>B))
		{
			memset(cnt,0,sizeof(cnt));
			l=b[i].l>>B<<B;r=m-1;ss=0;
			for(int j=l;j<=r;++cnt[a[j++]]);
			int lst;
			for(lst=now-1;!cnt[lst];--lst);
			for(int j=0;j<now;++j)if(cnt[j])lft[j]=lst,lst=j;
			for(lst=0;!cnt[lst];++lst);
			for(int j=now-1;j>=0;--j)if(cnt[j])rgt[j]=lst,lst=j;
			for(int j=0;j<now;++j)if(cnt[j])
				ss+=st[0][j]-qry(j,rgt[j]);
		}
		for(int j;r>b[i].r;--r)if(!--cnt[j=a[r]])
			ss-=st[0][j],
			ss-=qry(lft[j],rgt[j])-qry(lft[j],j)-qry(j,rgt[j]),
			rgt[lft[j]]=rgt[j],lft[rgt[j]]=lft[j];
		sss=ss;rsz=0;
		for(int j;l<b[i].l;++l)
		{
			j=a[l];
			rbk[rsz++]=(pr){cnt+j,cnt[j]};
			if(!--cnt[j])
			{
				sss-=st[0][j],
				sss-=qry(lft[j],rgt[j])-qry(lft[j],j)-qry(j,rgt[j]);
				rbk[rsz++]=(pr){rgt+lft[j],rgt[lft[j]]};
				rbk[rsz++]=(pr){lft+rgt[j],lft[rgt[j]]};
				rgt[lft[j]]=rgt[j],lft[rgt[j]]=lft[j];
			}
		}
		ans[b[i].id]=sss;
		for(l=b[i].l>>B<<B;rsz--;*rbk[rsz].first=rbk[rsz].second);
	}
	for(int i=0;i<q;printf("%lld\n",ans[i++]+1));
}

컴파일 시 표준 에러 (stderr) 메시지

tourism.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   39 | main()
      | ^~~~
tourism.cpp: In function 'int main()':
tourism.cpp:49:13: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   49 |   if(i+(1<<j-1)>=now)st[j][i]=st[j-1][i];
      |            ~^~
tourism.cpp:50:47: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   50 |   else st[j][i]=min(st[j-1][i],st[j-1][i+(1<<j-1)]);
      |                                              ~^~
tourism.cpp:51:37: warning: operation on 'a[i]' may be undefined [-Wsequence-point]
   51 |  for(int i=0;i<m;++i)read(a[i]),a[i]=dfn[--a[i]];
      |                                 ~~~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 41 / 41