Submission #789391

#	Time	Username	Problem	Language	Result	Execution time	Memory
789391		JakobZorz	Star Trek (CEOI20_startrek)	C++14	100 / 100	75 ms	22576 KiB

startrek

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <stack>
#include <limits.h>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <cstring>
#include <sstream>
 
#pragma GCC target("popcnt")
 
typedef long long ll;
typedef long double ld;
using namespace std;
const int MOD=1e9+7;
typedef pair<ll,ll>point;
//#define x first
//#define y second

ll powm(ll base,ll ex){
    base%=MOD;
    ex%=MOD-1;
    ll res=1;
    for(int p=0;p<64;p++){
        if(ex&(1LL<<p))
            res*=base;
        res%=MOD;
        base*=base;
        base%=MOD;
    }
    return res;
}

ll inv(ll n){
    return powm(n,MOD-2);
}


ll n;
ll d;
vector<int> nodes[100000];
int parents[100000];

int to(int a,int b){
    if(a==b)
        return a+200000;
    if(parents[a]==b)
        return a;
    return b+100000;
}

void init_parents(int node,int par){
    parents[node]=par;
    for(int ne:nodes[node]){
        if(ne==par)
            continue;
        init_parents(ne,node);
    }
}

bool dpt1[300000];
bool dp1[300000];

bool winning(int node,int par);

bool dpt3[100000];
int dp3[100000];

int get1(int node){
    if(dpt3[node])
        return dp3[node];
    
    int num=0;
    for(int ne:nodes[node]){
        if(ne==parents[node])
            continue;
        num+=!winning(ne,node);
    }
    dpt3[node]=true;
    dp3[node]=num;
    return num;
}

bool winning(int node,int par){
    int t=to(node,par);
    if(dpt1[t])
        return dp1[t];
    
    int num=get1(node);
    if(par!=parents[node]){
        if(node!=0)
            num+=!winning(parents[node],node);
        if(node!=par)
            num-=!winning(par,node);
    }
    
    bool res=num>0;
    dpt1[t]=true;
    dp1[t]=res;
    return res;
}

bool dpt2[300000];
int dp2[300000];

int count_critical(int node,int par);

bool dpt4[300000];
pair<int,pair<int,int>> dp4[300000];

pair<int,pair<int,int>> get2(int node){
    if(dpt4[node])
        return dp4[node];
    
    int l_count=0;
    int l_ch1=-1;
    int l_ch2=-1;
    
    for(int ne:nodes[node]){
        if(!winning(ne,node)){
            l_count++;
            if(l_ch1==-1)
                l_ch1=ne;
            else
                l_ch2=ne;
        }
    }
    
    dpt4[node]=false;
    dp4[node]={l_count,{l_ch1,l_ch2}};
    return{l_count,{l_ch1,l_ch2}};
}

bool dpt5[300000];
int dp5[300000];

int get3(int node){
    if(dpt5[node])
        return dp5[node];
    int res=1;
    for(int ne:nodes[node]){
        if(ne==parents[node])
            continue;
        res+=count_critical(ne,node);
    }
    dpt5[node]=true;
    dp5[node]=res;
    return res;
}

int count_critical(int node,int par){
    int t=to(node,par);
    if(dpt2[t])
        return dp2[t];
    
    int r=0;
    if(winning(node,par)){
        auto res=get2(node);
        
        int l_count=res.first;
        int l_ch1=res.second.first;
        int l_ch2=res.second.second;
        
        if(l_ch2==par)
            l_count--;
        
        if(l_ch1==par){
            l_count--;
            l_ch1=l_ch2;
        }
        
        if(l_count!=1)
            return 0;
        r=count_critical(l_ch1,node);
    }else{
        r=get3(node);
        if(par!=parents[node]){
            if(node!=0)
                r+=count_critical(parents[node],node);
            if(node!=par)
                r-=count_critical(par,node);
        }
    }
    dpt2[t]=true;
    dp2[t]=r;
    return r;
}

int main(){
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    
    //freopen("speeding.in","r",stdin);
    //freopen("speeding.out","w",stdout);
    
    cin>>n>>d;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        a--;b--;
        nodes[a].push_back(b);
        nodes[b].push_back(a);
    }
    init_parents(0,0);
    
    ll num_l=0;
    for(int i=0;i<n;i++)
        num_l+=!winning(i,i);
    
    ll E=0;
    for(int i=0;i<n;i++){
        ll res=count_critical(i,i);
        if(winning(i,i))
            E+=res;
        else
            E+=MOD-res;
        E%=MOD;
    }
    
    ll L=1;
    
    L*=powm(n,2*d)+MOD-powm(E,d);
    L%=MOD;
    
    L*=inv(n*n+MOD-E);
    L%=MOD;
    
    L*=num_l;
    L%=MOD;
    
    ll all_combs=powm(n,2*d);
    
    ll res=L*count_critical(0,0);
    res%=MOD;
    if(winning(0,0))
        res=all_combs+MOD-res;
    res%=MOD;
    cout<<res<<"\n";
    
    return 0;
}

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