Submission #1289504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289504		daffuwu	Star Trek (CEOI20_startrek)	C++20	38 / 100	49 ms	20388 KiB

startrek

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
//startrek

int n, u, v, ans, cnt[2], sz[100069];
long long d, wys[100069][2];
bool dp[100069], con[100069], more[100069];
vector<int> al[100069];
const int dv = 1e9+7;

int fe(int x, long long y)
{
    int res = 1;
    for (; y>0; y/=2)
    {
        if (y%2==1) res = 1ll*res*x%dv;
        x = 1ll*x*x%dv; 
    }
    return res;
}

void dfs(int u, int pv)
{
    sz[u] = 1;
    for (auto v:al[u])
    {
        if (v == pv) continue;
        dfs(v, u);
        if (!dp[v] && dp[u]) more[u] = 1;
        dp[u] |= !dp[v];
        sz[u] += sz[v];
    }
}

void dfs_r(int u, int pv)
{
    if (dp[u]) 
    {
        con[u] = 1;
        if (!con[pv]) more[u] = 1;
    } else con[u] = !more[pv];
    cnt[con[u]]++;
    for (auto v:al[u])
    {
        if (v == pv) continue;
        dfs_r(v, u);
    }
}

void dfs_dp(int u, int pv)
{
    wys[u][0] = cnt[1];
    vector<int> vc;
    for (auto v:al[u])
    {
        if (v == pv) continue;
        dfs_dp(v, u);
        wys[u][0] += wys[v][1];
        if (!dp[v]) vc.push_back(v);
    }
    if (dp[u])
    {
        if (vc.size()>1) wys[u][0] = 0;
        else wys[u][0] = wys[vc[0]][1]; 
    }
    wys[u][1] = 1ll*sz[u]*n-wys[u][0];
}

int main()
{
    int i;
    scanf("%d%lld", &n, &d);
    for (i=1; i<=n-1; i++)
    {
        scanf("%d%d", &u, &v);
        al[u].push_back(v);
        al[v].push_back(u);
    }
    dfs(1, 0);
    con[0] = more[0] = 1;
    dfs_r(1, 0);
    dfs_dp(1, 0);
    ans = wys[1][1]%dv;
    printf("%d\n", ans);
}   

Compilation message (stderr)

startrek.cpp: In function 'int main()':
startrek.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     scanf("%d%lld", &n, &d);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
startrek.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~

• 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