QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#233041 | #7607. The Doubling Game 2 | AFewSuns | WA | 2ms | 13892kb | C++14 | 3.0kb | 2023-10-31 11:45:35 | 2023-10-31 11:45:35 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
namespace my_std{
#define ll long long
#define bl bool
ll my_pow(ll a,ll b,ll mod){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
ll qpow(ll a,ll b){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res*=a;
a*=a;
b>>=1;
}
return res;
}
#define db double
#define pf printf
#define pc putchar
#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
#define go(u) for(ll i=head[u];i;i=e[i].nxt)
#define enter pc('\n')
#define space pc(' ')
#define fir first
#define sec second
#define MP make_pair
#define il inline
#define inf 8e18
#define random(x) rand()*rand()%(x)
#define inv(a,mod) my_pow((a),(mod-2),(mod))
il ll read(){
ll sum=0,f=1;
char ch=0;
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
sum=sum*10+(ch^48);
ch=getchar();
}
return sum*f;
}
il void write(ll x){
if(x<0){
x=-x;
pc('-');
}
if(x>9) write(x/10);
pc(x%10+'0');
}
il void writeln(ll x){
write(x);
enter;
}
il void writesp(ll x){
write(x);
space;
}
}
using namespace my_std;
#define mod 1000000007
ll n,head[300030],cnt=0,lg[300030],dp[300030][2],lst[300030][2];
ll siz[300030],f[300030][19],g[300030][19],h[300030];
struct node{
ll nxt,to;
}e[600060];
void add(ll u,ll v){
e[++cnt].nxt=head[u];
e[cnt].to=v;
head[u]=cnt;
}
void dfs(ll fa,ll u){
ll maxx=0,cmaxx=0;
siz[u]=1;
go(u){
ll v=e[i].to;
if(v==fa) continue;
dfs(u,v);
siz[u]+=siz[v];
if(siz[v]>=maxx){
cmaxx=maxx;
maxx=siz[v];
}
else if(siz[v]>=cmaxx) cmaxx=siz[v];
}
ll lim=lg[siz[u]];
if(maxx) lim=min(lim,lg[maxx]+1);
if(cmaxx) lim=min(lim,lg[cmaxx]+2);
fr(i,0,(1ll<<lim)-1) dp[i][0]=dp[i][1]=0;
dp[0][0]=1;
go(u){
ll v=e[i].to;
if(v==fa) continue;
fr(s,0,(1ll<<lim)-1){
fr(o,0,1){
lst[s][o]=dp[s][o];
dp[s][o]=dp[s][o]*h[v]%mod;
}
}
fr(j,0,lim-1){
if(f[v][j]){
fr(s,0,(1ll<<lim)-1){
if(s&(1ll<<j)) continue;
dp[s|(1ll<<j)][0]=(dp[s|(1ll<<j)][0]+lst[s][0])%mod;
if(s>(1ll<<j)) dp[s|(1ll<<j)][1]=(dp[s|(1ll<<j)][1]+lst[s][1])%mod;
}
}
if(g[v][j]){
fr(s,0,(1ll<<lim)-1){
if(s&(1ll<<j)) continue;
if(s<(1ll<<j)) dp[s|(1ll<<j)][1]=(dp[s|(1ll<<j)][1]+lst[s][0])%mod;
}
}
}
}
fr(i,0,lim) f[u][i]=dp[(1ll<<i)-1][0];
fr(i,0,lim){
fr(j,i+1,lim-1) g[u][i]=(g[u][i]+dp[(1ll<<(j+1))-1-(1ll<<i)][1])%mod;
if(i==lim) g[u][i]=(g[u][i]+dp[(1ll<<lim)-1][0])%mod;
else{
fr(j,i+1,lim) g[u][i]=(g[u][i]+dp[(1ll<<j)-1-(1ll<<i)][0])%mod;
}
}
fr(i,0,lim) h[u]=(h[u]+dp[(1ll<<i)-1][0])%mod;
fr(i,0,lim) h[u]=(h[u]+dp[(1ll<<i)-1][1])%mod;
}
int main(){
n=read();
fr(i,2,n){
ll u=read(),v=read();
add(u,v);
add(v,u);
}
lg[1]=0;
fr(i,2,n) lg[i]=lg[i>>1]+1;
dfs(0,1);
write(h[1]);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 13892kb
input:
5 1 2 1 3 1 4 4 5
output:
21
result:
ok single line: '21'
Test #2:
score: 0
Accepted
time: 2ms
memory: 11844kb
input:
1
output:
1
result:
ok single line: '1'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 13812kb
input:
128 11 32 116 81 65 4 117 47 5 81 104 30 61 8 82 59 95 20 92 29 29 127 97 39 123 33 59 128 115 33 83 67 74 16 77 33 64 73 124 123 8 127 61 51 101 122 35 90 119 116 112 27 81 93 109 123 54 1 119 100 116 16 65 47 67 27 22 105 76 87 36 39 27 96 72 31 91 123 21 105 118 12 110 48 121 72 14 115 24 16 106 ...
output:
126956802
result:
wrong answer 1st lines differ - expected: '508800953', found: '126956802'