oj.uz

Submission #667642

# Submission time Handle Problem Language Result Execution time Memory
667642 2022-12-01T20:44:13 Z berr Star Trek (CEOI20_startrek) C++17
23 / 100
 62 ms 12564 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);

    }
    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 3 ms 4948 KB Output is correct
2 Incorrect 48 ms 5120 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4948 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 3 ms 4948 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 4948 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 5140 KB Output is correct
8 Correct 50 ms 5172 KB Output is correct
9 Correct 35 ms 5116 KB Output is correct
10 Correct 46 ms 5028 KB Output is correct
11 Correct 50 ms 5076 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 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 5140 KB Output is correct
8 Correct 50 ms 5172 KB Output is correct
9 Correct 35 ms 5116 KB Output is correct
10 Correct 46 ms 5028 KB Output is correct
11 Correct 50 ms 5076 KB Output is correct
12 Incorrect 62 ms 12564 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 4948 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 5140 KB Output is correct
8 Correct 50 ms 5172 KB Output is correct
9 Correct 35 ms 5116 KB Output is correct
10 Correct 46 ms 5028 KB Output is correct
11 Correct 50 ms 5076 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Incorrect 48 ms 5112 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 4948 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 5140 KB Output is correct
8 Correct 50 ms 5172 KB Output is correct
9 Correct 35 ms 5116 KB Output is correct
10 Correct 46 ms 5028 KB Output is correct
11 Correct 50 ms 5076 KB Output is correct
12 Incorrect 62 ms 12564 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

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