Submission #597187

#	Time	Username	Problem	Language	Result	Execution time	Memory
597187		jasmin	Star Trek (CEOI20_startrek)	C++14	38 / 100	74 ms	16276 KiB

startrek

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int mod=1e9+7;

vector<int> win_down;
vector<int> redchild;
bool dfs_win(int v, int p, vector<vector<int> >& adi){
    for(auto u: adi[v]){
        if(u==p) continue;

        if(!dfs_win(u, v, adi)){
            redchild[v]=u;
            win_down[v]++;
        }
    }
    return win_down[v]>0;
}
vector<bool> win_up;
int violet=0;
void dfs_win2(int v, int p, vector<vector<int> >& adi){
    if(p==-1){
        win_up[v]=false;
    }
    else if(win_down[v]){
        if(win_down[p]==0 && !win_up[p]){
            win_up[v]=true;
        }
        else{
            win_up[v]=false;
        }
    }
    else if(win_down[v]==0){
        if(win_down[p]==1 && !win_up[p]){
            win_up[v]=true;
        }
        else{
            win_up[v]=false;
        }
    }
    if(!win_up[v] && !win_down[v]){
        //cout << "violet: " << v << "\n";
        violet++;
    } 

    for(auto u: adi[v]){
        if(u!=p) dfs_win2(u, v, adi);
    }
}

int redforce=0;
void dfs(int v, int p, vector<vector<int> >& adi){

    if(win_down[v]==0){
        //cout << "redforce: " << v << "\n";
        redforce++;
        for(auto u: adi[v]){
            if(u!=p) dfs(u, v, adi);
        }
    }
    else if(win_down[v]==1){
        dfs(redchild[v], v, adi);
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, d;
    cin >> n >> d;
    vector<vector<int> > adi(n);
    for(int i=0; i<n-1; i++){
        int a,b;
        cin >> a >> b;
        adi[a-1].push_back(b-1);
        adi[b-1].push_back(a-1);
    }

    win_up.resize(n, 0);
    redchild.resize(n, -1);
    win_down.resize(n, 0);
    bool we_win=dfs_win(0, -1, adi);
    dfs_win2(0, -1, adi);
    dfs(0, -1, adi);

   
    int ans=0;
    if(we_win){
        ans=(n*n-violet*redforce)%mod;
    }
    else{
        ans=(violet*redforce)%mod;
    }
    cout << ans << "\n";
}

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