QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#765661	#1288. Tokens on the Tree	MYLHF	TL	24ms	43836kb	C++14	2.3kb	2024-11-20 14:56:13	2024-11-20 14:56:19

Judging History

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

[2024-11-20 14:56:19]
评测

测评结果：TL
用时：24ms
内存：43836kb

查看

[2024-11-20 14:56:13]
提交

answer

#pragma GCC optimize(2,3,"Ofast")
#include<vector>
#include<bits/stdc++.h>
#define int long long
#define de(x) cout<<#x<<": "<<x<<endl
#define rep(i,a,b) for(int i(a);i<=(b);++i)
#define REP(i,a,b) for(int i(a);i>=(b);--i)
using namespace std;

const int N=1e6 +7,M=4e7;
int T,n,df[N],fa[N],ga[N];
int qpow[N],mark[N],cnt[11][11],ti;
vector<int> g[N];
inline int ck(int s,int i) { return (s/qpow[i-1])%3; }
inline int find(int u) { return u==fa[u] ? u : fa[u]=find(fa[u]); }
inline int fd(int u) { return u==ga[u] ? u : ga[u]=fd(ga[u]); }

inline int ck(int s)
{
	rep(i,1,n) ga[i]=i;
	rep(i,1,n) if(ck(s,i))
	{
		for(int j:g[i]) if(ck(s,j)==ck(s,i))
		{
			ga[fd(i)]=fd(j);
		}
	}
	
	int cnt[3]={};
	rep(i,1,n) cnt[ck(s,i)]=fd(i);
	rep(i,1,n) if(ck(s,i) && fd(i)!=cnt[ck(s,i)]) return 0;
	return 1;
}

inline void dfs(int s)
{
	if(mark[s]) return ;
	mark[s]=1,++ti;
	
	int but[3][12]={},can[3][12]={},d[12]={};
	
	rep(i,1,n) if(ck(s,i))
	{
		for(int j:g[i]) if(ck(s,i)==ck(s,j))
		{
			d[i]++;
		}
	}
	
	rep(i,1,n) if(!ck(s,i))
	{
		for(int j:g[i]) if(ck(s,j))
		{
			can[ck(s,j)][i]=1;
			if((d[j]==1)*j) but[ck(s,j)][i]=(d[j]==1)*j;
		}
	}
	
	
	rep(i,1,n) if(ck(s,i) && d[i]<=1) rep(j,1,n) if(!ck(s,j) && can[ck(s,i)][j])
	{
		if(i==but[ck(s,i)][j]) continue;
		int t=s-(ck(s,i)*qpow[i-1])+(ck(s,i)*qpow[j-1]);
		fa[find(s)]=find(t);
		dfs(t);
	}
}

signed main()
{
//	freopen("sort.in","r",stdin);
//	freopen("sort.out","w",stdout);
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	qpow[0]=1;
	rep(i,1,1000000) qpow[i]=qpow[i-1]*3;
	
	cin>>T;
	while(T--)
	{
		cin>>n;
		rep(i,2,n) cin>>df[i],g[i].emplace_back(df[i]),g[df[i]].emplace_back(i);
		if(n<=10)
		{
			rep(i,0,qpow[n]) fa[i]=i,mark[i]=0;
			rep(i,1,n) rep(j,1,n) cnt[i][j]=0;
			rep(ss,1,qpow[n]-1)
			{
				if(!ck(ss)) continue;
				int ret[3]={};
				rep(i,1,n) ret[(ss/qpow[i-1])%3]++;
				if(ret[1] && ret[2] && ck(ss)) dfs(ss);
			}
			
			rep(ss,1,qpow[n]-1)
			{
				if(!ck(ss)) continue;
				int ret[3]={};
				rep(i,1,n) ret[(ss/qpow[i-1])%3]++;
				if(ret[1] && ret[2] && ck(ss)) cnt[ret[1]][ret[2]]+=(find(ss)==ss);
			}
			
			int ret=0;
			rep(w,1,n-1) 
			{
				rep(b,1,n-w)
				{
					ret=(ret+cnt[w][b]*w*b)%M;
				}
			}
			cout<<ret<<endl;
			
			rep(i,1,n) g[i].clear();
		}
	}
	
		
	return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 24ms

memory: 43836kb

input:

2
5
1 2 3 3
10
1 2 3 4 3 6 3 8 2

output:

71
989

result:

ok 2 tokens

Test #2:

score: -100

Time Limit Exceeded

input:

33327
10
1 2 3 4 5 2 7 8 2
7
1 2 3 4 5 2
8
1 2 3 4 5 3 1
2
1
7
1 2 3 3 3 1
5
1 2 2 1
5
1 2 3 1
2
1
4
1 2 2
8
1 2 3 4 5 5 4
9
1 2 3 1 5 6 7 8
5
1 1 3 4
8
1 2 3 3 5 5 5
8
1 2 2 2 1 6 1
6
1 2 3 2 5
7
1 2 3 4 3 2
5
1 2 3 3
4
1 1 1
6
1 1 3 4 4
3
1 2
10
1 2 1 4 5 5 7 7 9
2
1
3
1 2
6
1 1 3 4 5
7
1 2 3 1 5 ...

output: