oj.uz

Submission #667643

# Submission time Handle Problem Language Result Execution time Memory
667643 2022-12-01T20:44:41 Z berr Star Trek (CEOI20_startrek) C++17
30 / 100
 64 ms 11440 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+37;
vector<int> adj[N], adj2[N];
int huh, huuh, mod=1e9+7;
int st[N][2], ans=0;
int mul(int x, int y){
    return (x*y)%mod;
}

int sum(int x, int y){
    return((x+y)%mod+mod)%mod;
}
int poww(int x, int y)
{
    if(y==0) return 1;
    int tmp=poww(x, y/2);

    if(y%2) return mul(tmp, mul(tmp, x));
    return mul(tmp, tmp); 
}

int dfs2(int v, int p, int d)
{
    int f=1;

    if(d%2==0) f=0;

    int count=0, val=0;

    for(auto i: adj2[v])
    {
        if(i==p) continue;

        if(dfs2(i, v, d+1))
        {
         
            if(d%2==0){
                f=1;
            }
        }
        else
        {
            if(d%2) f=0;
        }
    }


    return f;
}


int dfs(int v, int p, int d)
{
    int f=1;

    if(d%2==0) f=0;

    for(auto i: adj[v])
    {
        if(i==p) continue;

        if(dfs(i, v, d+1))
        {
            if(d%2==0){
                f=1;
            }
        }
        else
        {
            if(d%2) f=0;
        }
    }

    if(huh==v)
    {   
        if(st[huuh][((d+1)%2+2)%2]) 
        {
            if(d%2==0) f=1;
        }
        else
        {
            if(d%2) f=0;
        }
    }


    return f;
}


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

    int n, d; cin>>n>>d;


    for(int i=0; i<n-1; i++){
        int x, y; cin>>x>>y;

        adj[x].push_back(y);
        adj[y].push_back(x);

        adj2[x].push_back(y);
        adj2[y].push_back(x);
    }

    int ans=0;

    if(d>1)
    {
        cout<<poww(4, d);

    }

    else if(n<=1e4)
    {
        for(int i=1; i<=n; i++)
        {
            st[i][0]=dfs2(i, 0, 0);
            st[i][1]=dfs2(i, 0, 1);

        }

        int x=-1, y=-1, allx=0, ally=0;
        for(int i=1; i<=n; i++){
            if(st[i][0]) x=i, allx++;
            if(st[i][1]) y=i, ally++;
        }

        for(int i=1; i<=n; i++)
        {
            if(x!=-1){
                huh=i;
                huuh=x;

                if(dfs(1, 0, 0)) ans=sum(ans, allx);
            }
            if(y!=-1)
            {
                huh=i;
                huuh=y;
                if(dfs(1, 0, 0)) ans=sum(ans, ally);

            }

        }
        cout<<ans;

    }

   


}

Compilation message

startrek.cpp: In function 'long long int dfs2(long long int, long long int, long long int)':
startrek.cpp:30:9: warning: unused variable 'count' [-Wunused-variable]
   30 |     int count=0, val=0;
      |         ^~~~~
startrek.cpp:30:18: warning: unused variable 'val' [-Wunused-variable]
   30 |     int count=0, val=0;
      |                  ^~~

Subtask #1
0.0 / 0.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5016 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5016 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 58 ms 5136 KB Output is correct
8 Correct 52 ms 5164 KB Output is correct
9 Correct 33 ms 5076 KB Output is correct
10 Correct 46 ms 5096 KB Output is correct
11 Correct 49 ms 5096 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5016 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 58 ms 5136 KB Output is correct
8 Correct 52 ms 5164 KB Output is correct
9 Correct 33 ms 5076 KB Output is correct
10 Correct 46 ms 5096 KB Output is correct
11 Correct 49 ms 5096 KB Output is correct
12 Incorrect 64 ms 11440 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5016 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 58 ms 5136 KB Output is correct
8 Correct 52 ms 5164 KB Output is correct
9 Correct 33 ms 5076 KB Output is correct
10 Correct 46 ms 5096 KB Output is correct
11 Correct 49 ms 5096 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Incorrect 3 ms 5076 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5016 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 58 ms 5136 KB Output is correct
8 Correct 52 ms 5164 KB Output is correct
9 Correct 33 ms 5076 KB Output is correct
10 Correct 46 ms 5096 KB Output is correct
11 Correct 49 ms 5096 KB Output is correct
12 Incorrect 64 ms 11440 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

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