QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#423577	#7855. 不跳棋	kkkgjyismine4	64	2690ms	492696kb	C++14	2.9kb	2024-05-28 10:56:39	2024-05-28 10:56:41

Judging History

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

[2024-05-28 10:56:41]
评测

测评结果：64
用时：2690ms
内存：492696kb

查看

[2024-05-28 10:56:39]
提交

answer

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
const int inf=1e9;
ll ct[500050];
int n,tt,tt1,mark[1005000],dis[1005000][21],up[1005000][21],col[1005000][21],dep[1005000];
int mn[1005000],W[1005000];ll Ct[1005000];
vector<int>road[505000],vec[2][1005000];
vector<pii>Road[1005000];
void add(int u,int v,int w){Road[u].pb(mp(v,w)),Road[v].pb(mp(u,w));}
void dfs(int u,int fa){
	int lst=u;
	for(int v:road[u]){
		if(v==fa)continue;dfs(v,u);
		int id=++tt;add(lst,id,0),add(id,v,1),lst=id;
	}
}
void dfs1(int u,int fa){
	for(auto v:Road[u]){
		if(v.fi==fa)continue;
		dep[v.fi]=dep[u]+1;
		dfs1(v.fi,u);
	}
}
bool chk(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	return mark[u];
}
int sz[1000005],mx[1000005],rt,rt1,w1;
void find(int u,int fa,int ct1,int wf){
	sz[u]=1,mx[u]=0;
	for(auto v:Road[u]){
		if(v.fi==fa||chk(u,v.fi))continue;
		find(v.fi,u,ct1,v.se),sz[u]+=sz[v.fi];
	}mx[u]=max(ct1-sz[u],sz[u]);
	if(rt==-1||mx[u]<mx[rt])rt=u,rt1=fa,w1=wf;
}
int Mx[2],ctt[2][1005005],Now[1005005][2];
void init(int u,int fa,int cl,int dp,int id){
	up[u][dp]=id,col[u][dp]=cl,sz[u]=1;
	if(u<=n)++ctt[cl][dis[u][dp]],Mx[cl]=max(Mx[cl],dis[u][dp]);
	for(auto v:Road[u]){
		if(v.fi==fa||chk(u,v.fi))continue;
		dis[v.fi][dp]=dis[u][dp]+v.se;
		init(v.fi,u,cl,dp,id),sz[u]+=sz[v.fi];
	}
}
void solve(int u,int G,int dp){
	if(G<2)return;int p,q,s1,s2;
	rt=-1;find(u,-1,G,0),p=rt,q=rt1;
	assert(rt1>0);
    if(dep[p]<dep[q])swap(p,q);
    mark[p]=1,++tt1,Mx[0]=Mx[1]=0,dis[p][dp]=dis[q][dp]=0,W[tt1]=w1;
    init(p,-1,0,dp,tt1),init(q,-1,1,dp,tt1),s1=sz[p],s2=sz[q];
    mn[tt1]=W[tt1],Ct[tt1]=1;
    for(int i=0;i<2;++i){
    	vec[i][tt1].resize(Mx[i]+1);
    	for(int j=0;j<=Mx[i];++j)vec[i][tt1][j]=ctt[i][j],ctt[i][j]=0;
    	Now[tt1][i]=0;
    	while(Now[tt1][i]<=Mx[i]&&!vec[i][tt1][Now[tt1][i]])++Now[tt1][i];
    	if(Now[tt1][i]>Mx[i])mn[tt1]+=inf;
    	else mn[tt1]+=Now[tt1][i],Ct[tt1]*=1ll*vec[i][tt1][Now[tt1][i]];
	}
	if(mn[tt1]<=n)ct[mn[tt1]]+=Ct[tt1];
	solve(p,s1,dp+1),solve(q,s2,dp+1);
}
void upd(int p){
	if(mn[p]>n)return;
	ct[mn[p]]-=Ct[p],mn[p]=W[p],Ct[p]=1;
	for(int i=0;i<2;++i){
		while(Now[p][i]<vec[i][p].size()&&!vec[i][p][Now[p][i]])++Now[p][i];
		if(Now[p][i]==vec[i][p].size())mn[p]+=inf;
		else mn[p]+=Now[p][i],Ct[p]*=1ll*vec[i][p][Now[p][i]];
	}
	if(mn[p]<=n)ct[mn[p]]+=Ct[p];
}
void del(int p){
	for(int i=0;i<=20;++i){
		if(!up[p][i])continue;
		--vec[col[p][i]][up[p][i]][dis[p][i]],upd(up[p][i]);
	}
}
int Ans,tp;
ll lstans;
int main(){
	scanf("%d%d",&n,&tp),tt=n;
	for(int i=1;i<n;++i){
		int u,v;scanf("%d%d",&u,&v);
		road[u].pb(v),road[v].pb(u);
	}dfs(1,-1),dfs1(1,-1);
	solve(1,tt,0);
	int q=n-2;Ans=1;
	while(q--){
		ll x;scanf("%lld",&x);
		x^=(tp*lstans),del(x);
		while(!ct[Ans])++Ans;
		printf("%d %lld\n",Ans,ct[Ans]),lstans=ct[Ans];
	}
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 4

Accepted

time: 8ms

memory: 108456kb

input:

output:

result:

ok 98 lines

Test #2:

score: 4

Accepted

time: 4ms

memory: 108392kb

input:

output:

result:

ok 98 lines

Test #3:

score: 4

Accepted

time: 4ms

memory: 110376kb

input:

output:

result:

ok 98 lines

Test #4:

score: 4

Accepted

time: 15ms

memory: 108644kb

input:

output:

result:

ok 998 lines

Test #5:

score: 4

Accepted

time: 4ms

memory: 108548kb

input:

output:

result:

ok 998 lines

Test #6:

score: 4

Accepted

time: 16ms

memory: 110688kb

input:

output:

result:

ok 998 lines

Test #7:

score: 0

Wrong Answer

time: 860ms

memory: 274376kb

input:

output:

result:

wrong answer 199998th lines differ - expected: '23 1', found: '22 1'

Test #8:

score: 4

Accepted

time: 868ms

memory: 263220kb

input:

output:

result:

ok 199998 lines

Test #9:

score: 0

Wrong Answer

time: 846ms

memory: 273716kb

input:

output:

result:

wrong answer 199990th lines differ - expected: '14 2', found: '14 6'

Test #10:

score: 4

Accepted

time: 601ms

memory: 302300kb

input:

output:

result:

ok 199998 lines

Test #11:

score: 4

Accepted

time: 629ms

memory: 273212kb

input:

output:

result:

ok 199998 lines

Test #12:

score: 4

Accepted

time: 654ms

memory: 281028kb

input:

output:

result:

ok 199998 lines

Test #13:

score: 4

Accepted

time: 572ms

memory: 314644kb

input:

output:

result:

ok 199998 lines

Test #14:

score: 4

Accepted

time: 604ms

memory: 302312kb

input:

output:

result:

ok 199998 lines

Test #15:

score: 4

Accepted

time: 428ms

memory: 313492kb

input:

output:

result:

ok 199998 lines

Test #16:

score: 4

Accepted

time: 580ms

memory: 311124kb

input:

output:

result:

ok 199998 lines

Test #17:

score: 0

Wrong Answer

time: 806ms

memory: 272264kb

input:

output:

result:

wrong answer 199990th lines differ - expected: '15 1', found: '15 4'

Test #18:

score: 0

Wrong Answer

time: 925ms

memory: 272492kb

input:

output:

result:

wrong answer 199982nd lines differ - expected: '11 4', found: '10 1'

Test #19:

score: 4

Accepted

time: 633ms

memory: 280196kb

input:

output:

result:

ok 199998 lines

Test #20:

score: 4

Accepted

time: 642ms

memory: 277544kb

input:

output:

result:

ok 199998 lines

Test #21:

score: 0

Memory Limit Exceeded

input:

output:

2 124999250001
2 124998750003
2 124998250006
2 124997750010
2 124997250015
2 124996750021
2 124996250028
2 124995750036
2 124995250045
2 124994750055
2 124994250066
2 124993750078
2 124993250091
2 124992750105
2 124992250120
2 124991750136
2 124991250153
2 124990750171
2 124990250190
2 124989750210
...

result:

Test #22:

score: 0

Wrong Answer

time: 2597ms

memory: 491208kb

input:

output:

result:

wrong answer 198th lines differ - expected: '1 499600', found: '1 499601'

Test #23:

score: 0

Wrong Answer

time: 2600ms

memory: 490932kb

input:

output:

result:

wrong answer 25th lines differ - expected: '1 499946', found: '1 499945'

Test #24:

score: 0

Wrong Answer

time: 2598ms

memory: 492696kb

input:

output:

result:

wrong answer 1150th lines differ - expected: '1 497671', found: '1 497670'

Test #25:

score: 0

Wrong Answer

time: 2690ms

memory: 491404kb

input:

output:

result:

wrong answer 445th lines differ - expected: '1 499070', found: '1 499071'