oj.uz

Submission #534947

# Submission time Handle Problem Language Result Execution time Memory
534947 2022-03-09T07:45:55 Z leinad2 Star Trek (CEOI20_startrek) C++17
38 / 100
 105 ms 38972 KB 
#include<bits/stdc++.h>
using namespace std;
int n, i, j, k, a, b, d, A[2][2], mod=1e9+7;
vector<int>adj[100010], w[100010];
long long ans;
struct st
{
    int a, b;
};
st f(st a, st b)
{
    a.a=max(a.a, b.b);
    a.b=min(a.b, b.a);
    return a;
}
st dp[100010], dp2[100010][2][2], dp3[100010];
vector<st>pre[100010], suf[100010];
void dfs(int v, int par)
{
    dp[v].a=0;dp[v].b=1;
    for(auto p:adj[v])
    {
        if(p==par)continue;
        w[v].push_back(p);
        dfs(p, v);
        dp[v]=f(dp[v], dp[p]);
    }
}
void dfs2(int v, int par)
{
    int cnt=0;
    for(auto p:w[v])
    {
        for(int i=0;i<2;i++)for(int j=0;j<2;j++)
        {
            st a={0, 1};
            if(cnt>0)a=f(a, pre[v][cnt-1]);
            if(cnt+1<w[v].size())a=f(a, suf[v][cnt+1]);
            a=f(a, {i, j});
            dp2[p][i][j]=dp2[v][a.a][a.b];
        }
        cnt++;
        dfs2(p, v);
    }
}
void dfs3(int v, int par)
{
    int cnt=0;
    for(auto p:w[v])
    {
        st a={0, 1};
        if(v!=1)a=f(a, dp3[v]);
        if(cnt>0)a=f(a, pre[v][cnt-1]);
        if(cnt+1<w[v].size())a=f(a, suf[v][cnt+1]);
        dp3[p]=a;
        cnt++;
        dfs3(p, v);
    }
}
main()
{
    scanf("%d %d", &n, &d);
    for(i=0;++i<n;)
    {
        scanf("%d %d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1, 0);
    for(i=0;i++<n;)if(w[i].size())
    {
        st a={0, 1};
        pre[i].resize(w[i].size());
        suf[i].resize(w[i].size());
        for(j=0;j<w[i].size();j++)
        {
            a=f(a, dp[w[i][j]]);
            pre[i][j]={a.b, a.a};
        }
        a={0, 1};
        for(j=(int)w[i].size()-1;j>=0;j--)
        {
            a=f(a, dp[w[i][j]]);
            suf[i][j]={a.b, a.a};
        }
    }
    dp2[1][0][0]={0, 0};
    dp2[1][0][1]={0, 1};
    dp2[1][1][0]={1, 0};
    dp2[1][1][1]={1, 1};
    dfs2(1, 0);
    dfs3(1, 0);
    for(i=0;i++<n;)
    {
        st a={0, 1};
        for(auto p:w[i])
        {
            a=f(a, dp[p]);
        }
        if(i!=1)a=f(a, dp3[i]);
        dp3[i]=a;
    }
    for(i=0;i++<n;)A[dp3[i].a][dp3[i].b]++;
    for(i=0;i++<n;)
    {
        for(int j=0;j<2;j++)for(int k=0;k<2;k++)
        {
            st a=dp[i];
            a=f(a, {j, k});
            ans+=dp2[i][a.a][a.b].a*A[j][k];
        }
    }
    cout<<ans%mod;
}

Compilation message

startrek.cpp: In function 'void dfs2(int, int)':
startrek.cpp:38:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             if(cnt+1<w[v].size())a=f(a, suf[v][cnt+1]);
      |                ~~~~~^~~~~~~~~~~~
startrek.cpp: In function 'void dfs3(int, int)':
startrek.cpp:54:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         if(cnt+1<w[v].size())a=f(a, suf[v][cnt+1]);
      |            ~~~~~^~~~~~~~~~~~
startrek.cpp: At global scope:
startrek.cpp:60:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   60 | main()
      | ^~~~
startrek.cpp: In function 'int main()':
startrek.cpp:75:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(j=0;j<w[i].size();j++)
      |                 ~^~~~~~~~~~~~
startrek.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     scanf("%d %d", &n, &d);
      |     ~~~~~^~~~~~~~~~~~~~~~~
startrek.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Incorrect 6 ms 9804 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9676 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 5 ms 9700 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9692 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9624 KB Output is correct
6 Correct 5 ms 9804 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9700 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9692 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9624 KB Output is correct
6 Correct 5 ms 9804 KB Output is correct
7 Correct 6 ms 9804 KB Output is correct
8 Correct 5 ms 9932 KB Output is correct
9 Correct 6 ms 9804 KB Output is correct
10 Correct 6 ms 9824 KB Output is correct
11 Correct 6 ms 9956 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9700 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9692 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9624 KB Output is correct
6 Correct 5 ms 9804 KB Output is correct
7 Correct 6 ms 9804 KB Output is correct
8 Correct 5 ms 9932 KB Output is correct
9 Correct 6 ms 9804 KB Output is correct
10 Correct 6 ms 9824 KB Output is correct
11 Correct 6 ms 9956 KB Output is correct
12 Correct 97 ms 32120 KB Output is correct
13 Correct 105 ms 38972 KB Output is correct
14 Correct 78 ms 24344 KB Output is correct
15 Correct 96 ms 25528 KB Output is correct
16 Correct 99 ms 24816 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9700 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9692 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9624 KB Output is correct
6 Correct 5 ms 9804 KB Output is correct
7 Correct 6 ms 9804 KB Output is correct
8 Correct 5 ms 9932 KB Output is correct
9 Correct 6 ms 9804 KB Output is correct
10 Correct 6 ms 9824 KB Output is correct
11 Correct 6 ms 9956 KB Output is correct
12 Correct 5 ms 9696 KB Output is correct
13 Incorrect 8 ms 9804 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9700 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9692 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9624 KB Output is correct
6 Correct 5 ms 9804 KB Output is correct
7 Correct 6 ms 9804 KB Output is correct
8 Correct 5 ms 9932 KB Output is correct
9 Correct 6 ms 9804 KB Output is correct
10 Correct 6 ms 9824 KB Output is correct
11 Correct 6 ms 9956 KB Output is correct
12 Correct 97 ms 32120 KB Output is correct
13 Correct 105 ms 38972 KB Output is correct
14 Correct 78 ms 24344 KB Output is correct
15 Correct 96 ms 25528 KB Output is correct
16 Correct 99 ms 24816 KB Output is correct
17 Correct 5 ms 9696 KB Output is correct
18 Incorrect 8 ms 9804 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Incorrect 6 ms 9804 KB Output isn't correct
3 Halted 0 ms 0 KB -