Submission #3963654


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#include <cassert>

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;

#define pb push_back
#define rep(var,n)  for(int var=0;var<(n);++var)
#define found(s,e)  ((s).find(e)!=(s).end())

ll MOD;
ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }

vvi nxt;
unordered_map<ll,ll> memo;

ll f(int u, int v) {
    ll k = 131072LL * u + v;
    if (found(memo,k)) return memo[k];

    ll ans = 1;
    for (int w: nxt[v]) {
        if (w == u) continue;
        ans = MUL(ans, f(v, w));
    }
    return memo[k] = ADD(ans, 1);
}

void solve(int N,int M,vi& x,vi& y) {
    MOD = M;

    nxt.resize(N);
    rep(i,N-1){
        nxt[x[i]].pb(y[i]);
        nxt[y[i]].pb(x[i]);
    }

    rep(u,N){
        ll ans = 1;
        for (int v: nxt[u]) {
            ans = MUL(ans, f(u, v));
        }
        printf("%lld\n", ans);
    }
}

int main() {
    int N, M; scanf("%d%d", &N, &M);
    vi x(N-1), y(N-1);
    rep(i, N-1) {
        scanf("%d%d", &x[i], &y[i]);
        --x[i]; --y[i];
    }
    solve(N,M,x,y);
    return 0;
}

Submission Info

Submission Time
Task V - Subtree
User naoya_t
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1229 Byte
Status

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:54:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     int N, M; scanf("%d%d", &N, &M);
                                    ^
./Main.cpp:57:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x[i], &y[i]);
                                    ^

Test Cases

Set Name Score / Max Score Test Cases
All 0 / 100 0_00, 0_01, 0_02, 0_03, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17, 1_18, 1_19, 1_20, 1_21, 1_22, 1_23, 1_24, 1_25, 1_26, 1_27, 1_28, 1_29, 1_30, 1_31
Case Name Status Exec Time Memory
0_00 1 ms 256 KB
0_01 1 ms 256 KB
0_02 1 ms 256 KB
0_03 1 ms 256 KB
1_00 1 ms 256 KB
1_01 1 ms 256 KB
1_02 125 ms 18888 KB
1_03 131 ms 19144 KB
1_04
1_05
1_06
1_07
1_08
1_09
1_10
1_11
1_12 1300 ms 15432 KB
1_13 1303 ms 16200 KB
1_14 256 ms 15304 KB
1_15 262 ms 16072 KB
1_16 145 ms 14792 KB
1_17 152 ms 15944 KB
1_18 134 ms 15048 KB
1_19 143 ms 15816 KB
1_20 142 ms 14792 KB
1_21 135 ms 15688 KB
1_22 127 ms 14920 KB
1_23 135 ms 15688 KB
1_24 132 ms 14664 KB
1_25 130 ms 15688 KB
1_26 132 ms 15176 KB
1_27 130 ms 15560 KB
1_28 139 ms 16584 KB
1_29 133 ms 16712 KB
1_30 123 ms 17480 KB
1_31 150 ms 20040 KB