Submission #1132850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132850		ackhava	Star Trek (CEOI20_startrek)	C++20	58 / 100	1099 ms	327680 KiB

startrek

#pragma GCC optimize "O3,unroll-loops"
#pragma GCC target "abm,bmi,bmi2,popcnt,lzcnt,avx,avx2,tune=native"
#include <bits/stdc++.h>
#define REP(v, i, j) for (int v = i; v != j; v++)
#define FORI(v) for (auto i : v)
#define FORJ(v) for (auto j : v)

#define OUT(v, a) \
    FORI(v)       \
    cout << i << a;
#define OUTS(v, a, b)      \
    cout << v.size() << a; \
    OUT(v, b)
#define in(a, n) \
    REP(i, 0, n) \
    cin >> a[i];

#define SORT(v) sort(begin(v), end(v))
#define REV(v) reverse(begin(v), end(v))
#define MEMSET(m) memset(m, -1, sizeof m)

#define pb push_back
#define fi first
#define se second

#define detachIO                      \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0);
    
using namespace std;

template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
bool operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
    if(__x.size() != __y.size()) return false;
    return std::equal(__x.begin(), __x.end(), __y.begin());
}


typedef pair<long long, long long> pii;
typedef pair<pii, long long> piii;
typedef pair<pii, pii> piiii;

const long long MOD = 1e9+7;

size_t hash_combine( size_t lhs, size_t rhs ) {
  if constexpr (sizeof(size_t) >= 8) {
    lhs ^= rhs + 0x517cc1b727220a95 + (lhs << 6) + (lhs >> 2);
  } else {
    lhs ^= rhs + 0x9e3779b9 + (lhs << 6) + (lhs >> 2);
  }
  return lhs;
}

namespace std {
    template <typename T, typename U>
    struct hash<std::pair<T,U>> {
    public:
    std::size_t operator()(const std::pair<T, U> &x) const
    {
        return hash_combine(std::hash<T>()(x.first), std::hash<U>()(x.second));
    }
    };
}


vector<long long> adj[200100];
long long memo1[200100];
bool memo2[200100];
long long memo3[200100][2];
long long parent[200100];
long long memof[200100];
long long override=-1;
long long root=1;
bool overdata=false;

vector<long long> memov[200100];
long long memos[200100];
long long memon[200100][2];
unordered_map<pair<pii,bool>,long long> num_winning_memo;
unordered_map<pair<pii,bool>,long long> is_winning_memo;
bool has_parent[200100];

bool winning(long long node, long long parent){
    if(parent==-1)root=node;
    if(node==override)return overdata;
    bool ans=false;
    memo1[node]=0;
    FORI(adj[node]){
        if(i!=parent)ans=(not winning(i,node)) or ans,memo1[node]+=!memo1[i];
    }
    // cerr<<node<<": "<<ans<<'\n';
    ::parent[node]=parent;
    return ans;
}

void update(long long node, long long parent, bool dp){
    long long onset=0;
    if(!dp)onset++;
    FORI(adj[node]){
        if(i!=parent && !memo1[i])onset++;
    }
    memo2[node]=dp;
    memof[node]=onset;
    FORI(adj[node]){
        if(i==parent)continue;
        if(!memo1[i])onset--;
        update(i,node,onset);
        if(!memo1[i])onset++;
    }

    // long long ans=0;
    if(!dp)onset--;
    is_winning_memo[{{node,parent},true}]=onset;
    if(!dp)onset++;
    FORI(adj[node]){
        if(i==parent)continue;
        if(!memo1[i])onset--;
        is_winning_memo[{{node,i},true}]=onset;
        if(!memo1[i])onset++;
    }

    onset++;
    if(!dp)onset--;
    is_winning_memo[{{node,parent},false}]=onset;
    if(!dp)onset++;
    FORI(adj[node]){
        if(i==parent)continue;
        if(!memo1[i])onset--;
        is_winning_memo[{{node,i},false}]=onset;
        if(!memo1[i])onset++;
    }
    onset--;

    if(is_winning_memo[{{node,parent},true}])num_winning_memo[{{node,parent},true}]++;
    FORI(adj[node]){
        if(i==parent)continue;
        num_winning_memo[{{node,parent},true}]+=num_winning_memo[{{i,node},is_winning_memo[{{node,parent},true}]-(!memo1[i])}];
        memon[node][true] += num_winning_memo[{{i,node},true}];
    }

    if(is_winning_memo[{{node,parent},false}])num_winning_memo[{{node,parent},false}]++;
    FORI(adj[node]){
        if(i==parent)continue;
        num_winning_memo[{{node,parent},false}]+=num_winning_memo[{{i,node},is_winning_memo[{{node,parent},false}]-(!memo1[i])}];
        memon[node][false] += num_winning_memo[{{i,node},false}];
    }
}

void update2(long long node, long long parent){
    set<int> st;

    if(!memo2[node])st.insert(parent);

    FORI(adj[node]){
        if(i!=parent && !memo1[i])st.insert(i);
    }
    FORI(adj[node]){
        if(i==parent)memon[node][true ]+=num_winning_memo[{{parent,node},true }];
        if(i==parent)memon[node][false]+=num_winning_memo[{{parent,node},false}];
    }
    FORI(adj[node]){
        if(i!=parent){
            st.insert(i);
            bool b=st.size();
            num_winning_memo[{{node,i},false}] = memon[node][(bool)b] - num_winning_memo[{{i,node},b}];
            if(b)num_winning_memo[{{node,i},false}]++;
            // if(st.size()==1){
            //     num_winning_memo[{{node,i},false}] -= num_winning_memo[{{*st.begin(),node},b}];
            //     num_winning_memo[{{node,i},false}] += num_winning_memo[{{*st.begin(),node},false}];
            // }
            st.erase(i);
            b=st.size();
            num_winning_memo[{{node,i},true }] = memon[node][(bool)b] - num_winning_memo[{{i,node},b}];
            if(b)num_winning_memo[{{node,i},true }]++;
            if(st.size()==1){
                num_winning_memo[{{node,i},true }] -= num_winning_memo[{{*st.begin(),node},b}];
                num_winning_memo[{{node,i},true }] += num_winning_memo[{{*st.begin(),node},false}];
            }
            if(!memo1[i])st.insert(i);

            update2(i,node);
        }
    }
}

bool dp(long long node, bool b){
    if(node==root)return b;
    if(memo3[node][b]!=-1)return memo3[node][b];
    if(b == (bool)(memo1[node]))return (memo3[node][b]=memo1[root]);
    if(b && !memo1[node] && memo1[parent[node]]==1){
        return (memo3[node][b]=dp(parent[node],false));
    }
    if(!b && memo1[node] && memo1[parent[node]]==0){
        return (memo3[node][b]=dp(parent[node],true));
    }
    return (memo3[node][b]=dp(parent[node],memo1[parent[node]]));
}


piiii multiply(piiii a, piiii b){
    piiii c;
    c.fi.fi=c.fi.se=c.se.fi=c.se.se;

    c.fi.fi = (a.fi.fi *b.fi.fi + a.fi.se *b.se.fi)%MOD;
    c.se.fi = (a.se.fi *b.fi.fi + a.se.se *b.se.fi)%MOD;
    c.fi.se = (a.fi.fi *b.fi.se + a.fi.se *b.se.se)%MOD;
    c.se.se = (a.se.fi *b.fi.se + a.se.se *b.se.se)%MOD;

    return c;
}

piiii exp(piiii mat, int x){
    if(x==1)return mat;
    if(x==2)return multiply(mat,mat);
    if(x==3)return multiply(mat,multiply(mat,mat));
    if(x==3)return multiply(multiply(mat,mat),multiply(mat,mat));
    piiii res = exp(mat,x/2);
    res=multiply(res,res);
    if(x&1)res=multiply(res,mat);
    return res;
}

int main(){
    detachIO;
    // freopen("out.txt", "r", stdin);
    long long n;cin>>n;
    long long d;cin>>d;
    REP(i,1,n){
        long long u,v;cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    long long w=0,l=0;
    MEMSET(memof);
    winning(1,-1);
    update(1,-1,true);
    REP(i,1,n+1){
        assert(memof[i]!=-1);
        // assert(((bool)memof[i])==winning(i,-1));
        if(memof[i])w++;
        else l++;
    }
    // cerr<<endl;

    // TODO: Matrix expo

    piiii mat;

    if(d>1){
        num_winning_memo.clear();
        is_winning_memo.clear();
        memset(memon,0,sizeof memon);
        memset(memof,0,sizeof memof);
        memset(memos,0,sizeof memos);
        memset(memo3,0,sizeof memo3);
        winning(1,-1);
        update(1,-1,true);
        update2(1,-1);
        REP(j,1,n+1){
            mat.se.se += n-1;
            mat.fi.se ++;
            FORI(adj[j]){
                mat.se.se -= num_winning_memo[{{i,j},true}];
                mat.fi.se += num_winning_memo[{{i,j},true}];
            }
            // cerr<<i<<" -> "<<dp(i,true)<<", "<<parent[i]<<", "<<memo1[i]<<'\n';
        }
        // cerr<<mat.fi.fi<<"\t"<<mat.fi.se<<'\n';
        // cerr<<mat.se.fi<<"\t"<<mat.se.se<<'\n';
        // REP(j,1,n+1){
        //     num_winning_memo.clear();
        //     is_winning_memo.clear();
        //     memset(memon,0,sizeof memon);
        //     memset(memof,0,sizeof memof);
        //     memset(memos,0,sizeof memos);
        //     memset(memo3,0,sizeof memo3);
        //     winning(j,-1);
        //     update(j,-1,true);
        //     MEMSET(memo3);
        //     REP(i,1,n+1){
        //         if(dp(i,true))mat.fi.se--;
        //         else mat.se.se--;
        //         // cerr<<i<<" -> "<<dp(i,true)<<", "<<parent[i]<<", "<<memo1[i]<<'\n';
        //     }
        // }
        // // cerr<<mat.fi.fi<<"\t"<<mat.fi.se<<'\n';
        // // cerr<<mat.se.fi<<"\t"<<mat.se.se<<'\n';
        // assert(mat.fi.se==0);
        // assert(mat.se.se==0);
        // REP(j,1,n+1){
        //     num_winning_memo.clear();
        //     is_winning_memo.clear();
        //     memset(memon,0,sizeof memon);
        //     memset(memof,0,sizeof memof);
        //     memset(memos,0,sizeof memos);
        //     memset(memo3,0,sizeof memo3);
        //     winning(j,-1);
        //     update(j,-1,true);
        //     MEMSET(memo3);
        //     REP(i,1,n+1){
        //         if(dp(i,true))mat.fi.se++;
        //         else mat.se.se++;
        //         // cerr<<i<<" -> "<<dp(i,true)<<", "<<parent[i]<<", "<<memo1[i]<<'\n';
        //     }
        // }
        MEMSET(memof);
        num_winning_memo.clear();
        is_winning_memo.clear();
        memset(memon,0,sizeof memon);
        memset(memof,0,sizeof memof);
        memset(memos,0,sizeof memos);
        memset(memo3,0,sizeof memo3);
        winning(1,-1);
        update(1,-1,true);
        REP(i,1,n+1){
            assert(memof[i]!=-1);
            if(memof[i])mat.fi.fi+=n;
            else mat.se.fi+=n;
        }
    }

    mat.fi.fi %= MOD;
    mat.fi.se %= MOD;
    mat.se.fi %= MOD;
    mat.se.se %= MOD;

    if(d>1){
        mat = exp(mat,d-1);
        long long w2,l2;
        w2=mat.fi.fi * w + mat.fi.se * l;
        w2%=MOD;
        l2=mat.se.fi * w + mat.se.se * l;
        l2%=MOD;
        w=w2,l=l2;
    }

    // REP(i,0,d-1){
    // }

    long long ans=0;
    winning(1,-1);
    update(1,-1,true);
    MEMSET(memo3);
    REP(i,1,n+1){
        if(dp(i,true))ans+=l;
        // cerr<<i<<" -> "<<dp(i,true)<<", "<<parent[i]<<", "<<memo1[i]<<'\n';
    }
    override=-1;
    overdata=true;
    const bool r=winning(1,-1);
    REP(i,1,n+1){
        if(r)ans+=w;
    }
    cout<<ans%MOD<<'\n';
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 20 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 15