QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#235563#7607. The Doubling Game 2kkioCompile Error//C++1710.1kb2023-11-02 21:52:182023-11-02 21:52:18

Judging History

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

  • [2023-11-02 21:52:18]
  • 评测
  • [2023-11-02 21:52:18]
  • 提交

answer

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("Ofast","unroll-loops","inline","no-stack-protector")
#include <bits/stdc++.h>
using namespace std;
namespace Def{
    #define fir first
    #define sec second
    #define lson (tr[i].ls)
    #define rson (tr[i].rs)
    #define FIO(file) freopen(file".in","r",stdin), freopen(file".out","w",stdout)
    #define Untie() ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
    typedef long long ll;
    typedef double db;
    typedef long double ldb;
    typedef unsigned int uint;
    typedef unsigned long long ull;
    typedef pair<int,int> pii;
    typedef pair<ll,ll> pll;
    typedef __int128_t i128;
}
using namespace Def;
namespace FastIO {
	struct IO {
	    char ibuf[(1 << 20) + 1], *iS, *iT, obuf[(1 << 20) + 1], *oS;
	    IO() : iS(ibuf), iT(ibuf), oS(obuf) {} ~IO() { fwrite(obuf, 1, oS - obuf, stdout); }
		#if ONLINE_JUDGE
		#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
		#else
		#define gh() getchar()
		#endif
		inline bool eof (const char &ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == 't' || ch == EOF; }
	    inline long long read() {
	        char ch = gh();
	        long long x = 0;
	        bool t = 0;
	        while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
	        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
	        return t ? ~(x - 1) : x;
	    }
	    inline void read (char *s) {
	    	char ch = gh(); int l = 0;
	    	while (eof(ch)) ch = gh();
	    	while (!eof(ch)) s[l++] = ch, ch = gh();
	    }
	    inline void read (double &x) {
	    	char ch = gh(); bool t = 0;
	    	while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
	    	while (ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = gh();
	    	if (ch != '.') return t && (x = -x), void(); ch = gh();
	    	for (double cf = 0.1; '0' <= ch && ch <= '9'; ch = gh(), cf *= 0.1) x += cf * (ch ^ 48);
	    	t && (x = -x);
	    }
	    inline void pc (char ch) {
	    	#ifdef ONLINE_JUDGE
	    	if (oS == obuf + (1 << 20) + 1) fwrite(obuf, 1, oS - obuf, stdout), oS = obuf; 
	    	*oS++ = ch;
	    	#else
	    	putchar(ch);
	    	#endif
		}
        inline void write (char *s)
        {
            int len = strlen(s);
            for(int i = 0; i < len; i++)pc(s[i]);
        }
		template<typename _Tp>
	    inline void write (_Tp x) {
	    	static char stk[64], *tp = stk;
	    	if (x < 0) x = ~(x - 1), pc('-');
			do *tp++ = x % 10, x /= 10;
			while (x);
			while (tp != stk) pc((*--tp) | 48);
	    }
	    inline void puts(const char *s){
			int len = strlen(s);
			for (int i = 0; i < len; i++)pc(s[i]);
		}
	} io;
	inline long long read () { return io.read(); }
	template<typename Tp>
	inline void read (Tp &x) { io.read(x); }
	template<typename _Tp>
	inline void write (_Tp x) { io.write(x); }
}
using namespace FastIO;
namespace misc{
    constexpr int infi=1e9;
    constexpr int minfi=0x3f3f3f3f;
    constexpr ll infl=1e18;
    constexpr ll minfl=0x3f3f3f3f3f3f3f3f;
    constexpr int mod=1e9+7;
    constexpr int inv2=(mod+1)/2;
    constexpr int inv3=(mod+1)/3;
    mt19937_64 rnd(0x3494393);
    template<typename T,typename E>
        inline T ksm(T b,E p){T ret=1;while(p){if(p&1)ret=1ll*ret*b%mod;b=1ll*b*b%mod;p>>=1;}return ret;}
    template<typename T,typename E> 
        inline T ginv(T v){return ksm(v,mod-2);}
    template<typename T,typename E>
        inline void cmax(T &a,E b){a<b?(a=b,1):0;}
    template<typename T,typename E>
        inline void cmin(T &a,E b){a>b?(a=b,1):0;}
    template<typename T,typename E>
        inline void cadd(T &a,E b){(a+=b)>=mod?(a-=mod):0;}
    template<typename T,typename E>
        inline void csub(T &a,E b){(a-=b)<0?(a+=mod):0;}
    template<typename T,typename E>
        inline void cmul(T &a,E b){a=1ll*a*b%mod;}
    template<typename T,typename E>
        inline T madd(T a,E b){return (a+=b)>=mod?(a-mod):a;}
    template<typename T,typename E>
        inline T msub(T a,E b){return (a-=b)<0?(a+mod):a;}
    template<typename T,typename E>
        inline T mmul(T a,E b){return 1ll*a*b%mod;}
    template<typename T>
        struct dseg{T *first,*last;dseg(T* _l,T* _r):first(_l),last(_r){}};
    inline void debug(void){cerr<<'\n';}
    template<typename T,typename... arg>
        inline void debug(T x,arg... r){cerr<<x<<' ';debug(r...);}
    template<typename T,typename... arg>
        inline void debug(dseg<T> A,arg... v){cerr<<"[ ";for(T* i=A.first;i!=A.last;++i)cerr<<*i<<' ';cerr<<"] ";debug(v...);}
    template<typename T>
        inline T randseg(T l,T r){assert(l<=r);return rnd()%(r-l+1)+l;}
    template<typename T>
        inline bool gbit(T v,int bit){return v>>bit&1;}
    inline ll gcd(ll a,ll b){if(!b||!a) return a+b;ll az=__builtin_ctz(a),bz=__builtin_ctz(b),z=(az>bz)?bz:az,t;b>>=bz;while(a) a>>=az,t=a-b,az=__builtin_ctz(t),b=a<b?a:b,a=t<0?-t:t;return b<<z;}
    inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1,y=0;return a;}ll g=exgcd(b,a%b,y,x);y-=x*(a/b);return g;}
    inline ll Sum1(ll n){return n*(n+1)/2;}
    inline ll Sum2(ll n){return n*(n+1)*(2*n+1)/6;}
    inline ll Sqr(ll n){return n*n;}
    #define binom(n,m) (n<0||m<0||n<m?0:1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod)
    #define likely(x) (__builtin_expect(!!(x),1))
    #define unlikely(x) (__builtin_expect(!!(x),0))
}
using namespace misc;
namespace WVector{
    template<typename T,std::size_t MAXN>
    class SmallVector
    {
    private:
        char mem[MAXN*sizeof(T)];
        std::size_t n;
    public:
        using size_type=std::size_t;
        using diffrence_type=std::ptrdiff_t;
        using value_type=T;
        using pointer=T*;
        using const_pointer=const T*;
        using reference=T&;
        using const_reference=const T&;
        using iterator=T*;
        using const_iterator=const T*;
        using reverse_iterator=T*;
        using const_reverse_iterator=const T*;

        SmallVector(): mem{},n{} {}
        ~SmallVector() { while(n) pop_back(); }
        SmallVector(const std::initializer_list<T> &ils): mem{},n{}
        { for(auto &i: ils) push_back(i); }
        size_type size()const
        { return n; }
        size_type max_size()const
        { return MAXN; }
        bool empty()const
        { return !n; }
        void push_back(const_reference x)
        { new(end()) T(x),n++; }
        template<typename ...Args>
        reference emplace_back(Args &&...args)
        { return new(end()) T(forward<Args&&>(args)...),n++,back(); }
        void pop_back()
        { back().~T(),n--; }
    #define PTR_CAST(Ptr,p) static_cast<Ptr>(static_cast<void*>(p))
    #define CPTR_CAST(Ptr,p) static_cast<Ptr>(static_cast<const void*>(p))
        reference operator [](std::size_t i)
        { return *static_cast<T*>(mem+i*sizeof(T)); }
        reference front()
        { return *begin(); }
        reference back()
        { return *(end()-1); }
        iterator begin()
        { return PTR_CAST(iterator,mem); }
        iterator end()
        { return PTR_CAST(iterator,mem+n*sizeof(T)); }
        reverse_iterator rbegin()
        { return PTR_CAST(reverse_iterator,mem+(n-1)*sizeof(T)); }
        reverse_iterator rend()
        { return PTR_CAST(reverse_iterator,mem-sizeof(T)); }
        pointer data()
        { return PTR_CAST(pointer,mem); }
        const_reference operator[](std::size_t i)const
        { return *static_cast<const T*>(mem+i*sizeof(T)); }
        const_reference front()const
        { return *begin(); }
        const_reference back()const
        { return *(end()-1); }
        const_iterator begin()const
        { return CPTR_CAST(const_iterator,mem); }
        const_iterator end()const
        { return CPTR_CAST(const_iterator,mem+n*sizeof(T)); }
        const_reverse_iterator rbegin()const
        { return CPTR_CAST(const_reverse_iterator,mem+(n-1)*sizeof(T)); }
        const_reverse_iterator rend()const
        { return CPTR_CAST(const_reverse_iterator,mem-sizeof(T)); }
        const_pointer data()const
        { return CPTR_CAST(const_pointer,mem); }
    #undef PTR_CAST
    #undef CPTR_CAST
    };
}
using Svector=WVector::SmallVector<int,20>; 
const int maxn=3e5+10;
int n;
vector<int> G[maxn];
Svector f[maxn],g[maxn];
int h[maxn];
int dp[2][(1<<18)][2];
void dfs(int u,int fa)
{
    for(int i=0;i<G[u].size();i++)
    {
        if(G[u][i]==fa)swap(G[u].back(),G[u][i]),G[u].pop_back(),i--;
        else dfs(G[u][i],u);
    }
    sort(G[u].begin(),G[u].end(),[&](int a,int b){return f[a].size()<f[b].size();});
    int o=0,nowm=0;dp[0][0][0]=1,dp[0][0][1]=0;
    for(int t=0;t<G[u].size();t++)
    {
        int v=G[u][t],mem=f[v].size();
        for(int S=0;S<(1<<mem);S++)dp[o^1][S][0]=dp[o^1][S][1]=0;
        for(int S=0;likely(S<(1<<nowm));S++)
        {
            cadd(dp[o^1][S][0],mmul(dp[o][S][0],h[v]));
            cadd(dp[o^1][S][1],mmul(dp[o][S][1],h[v]));
            for(int i=0;i<mem;i++)
                if(!gbit(S,i))
                {
                    cadd(dp[o^1][S|(1<<i)][0],mmul(dp[o][S][0],f[v][i]));
                    if(S>(1<<i))cadd(dp[o^1][S|(1<<i)][1],mmul(dp[o][S][1],f[v][i]));
                    else cadd(dp[o^1][S|(1<<i)][1],mmul(dp[o][S][0],g[v][i]));
                }
        }
        nowm=mem;
        
        o^=1;
    }
    int sz=nowm+1;
    f[u].resize(sz),g[u].resize(sz);
    for(int i=0;i<sz;i++)
    {
        int w=(1<<i)-1;
        cadd(h[u],dp[o][w][0]);
        cadd(h[u],dp[o][w][1]);
        cadd(f[u][i],dp[o][w][0]);
        cadd(g[u][i],dp[o][w][0]);
        for(int j=0;j<i-1;j++)cadd(g[u][j],dp[o][w^(1<<j)][0]),cadd(g[u][j],dp[o][w^(1<<j)][1]);
    }
    while(!f[u].back()&&!g[u].back())f[u].pop_back(),g[u].pop_back();
    // debug("!",u);
    // for(int i=0;i<f[u].size();i++)
    //     debug(f[u][i],g[u][i]);
    // debug(h[u]);
}
int main(){
    n=read();
    for(int i=1,u,v;i<n;i++)
    {
        u=read(),v=read();
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    write(h[1]),io.pc('\n');
}

Details

answer.code: In function ‘void dfs(int, int)’:
answer.code:248:10: error: ‘using Svector = class WVector::SmallVector<int, 20>’ {aka ‘class WVector::SmallVector<int, 20>’} has no member named ‘resize’; did you mean ‘size’?
  248 |     f[u].resize(sz),g[u].resize(sz);
      |          ^~~~~~
      |          size
answer.code:248:26: error: ‘using Svector = class WVector::SmallVector<int, 20>’ {aka ‘class WVector::SmallVector<int, 20>’} has no member named ‘resize’; did you mean ‘size’?
  248 |     f[u].resize(sz),g[u].resize(sz);
      |                          ^~~~~~
      |                          size
answer.code: In instantiation of ‘T& WVector::SmallVector<T, MAXN>::operator[](std::size_t) [with T = int; long unsigned int MAXN = 20; WVector::SmallVector<T, MAXN>::reference = int&; std::size_t = long unsigned int]’:
answer.code:238:70:   required from here
answer.code:176:19: error: invalid ‘static_cast’ from type ‘char*’ to type ‘int*’
  176 |         { return *static_cast<T*>(mem+i*sizeof(T)); }
      |                   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~