oj.uz

Submission #597187

# Submission time Handle Problem Language Result Execution time Memory
597187 2022-07-15T16:57:57 Z jasmin Star Trek (CEOI20_startrek) C++14
38 / 100
 74 ms 16276 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 2 ms 324 KB Output is correct
8 Correct 1 ms 448 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 2 ms 324 KB Output is correct
8 Correct 1 ms 448 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 74 ms 12236 KB Output is correct
13 Correct 64 ms 16276 KB Output is correct
14 Correct 41 ms 8732 KB Output is correct
15 Correct 47 ms 8892 KB Output is correct
16 Correct 63 ms 8908 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 2 ms 324 KB Output is correct
8 Correct 1 ms 448 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 2 ms 324 KB Output is correct
8 Correct 1 ms 448 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 74 ms 12236 KB Output is correct
13 Correct 64 ms 16276 KB Output is correct
14 Correct 41 ms 8732 KB Output is correct
15 Correct 47 ms 8892 KB Output is correct
16 Correct 63 ms 8908 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Incorrect 1 ms 340 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -