Submission #1349503


Source Code Expand

#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
typedef long long int64;
static const int MAXN = 52;
static const int MAXM = 202;
static const int MAXK = 102;
static const int MODULUS = 1e9 + 7;
#define _  %  MODULUS
#define __ %= MODULUS

template <typename T> inline T gcd(const T a, const T b) { return b == 0 ? a : gcd<T>(b, a % b); }

int64 fact[MAXM + MAXK], fact_inv[MAXM + MAXK];
inline int64 fpow(int64 base, int exp)
{
    int64 ans = 1;
    for (; exp; exp >>= 1, (base *= base)__) if (exp & 1) (ans *= base)__;
    return ans;
}
inline void preprocess()
{
    fact[0] = 1;
    for (int i = 1; i < MAXM + MAXK; ++i) fact[i] = fact[i - 1] * i _;
    fact_inv[MAXM + MAXK - 1] = fpow(fact[MAXM + MAXK - 1], MODULUS - 2);
    for (int i = MAXM + MAXK - 2; i >= 0; --i) fact_inv[i] = fact_inv[i + 1] * (i + 1)_;
}
inline int64 binom(int n, int m)
{
    if (n < m) return 0; else return fact[n] * fact_inv[n - m]_ * fact_inv[m]_;
}

int n, m, k;
int head[MAXN], dest[MAXM], next[MAXM];

inline void add_edge(int u, int v)
{
    static int w = 0;
    dest[w] = v; next[w] = head[u]; head[u] = w++;
}

int dfn[MAXN], low[MAXN];
int stk[MAXN], top = 0;
std::vector<int> bcc[MAXN];
int bcc_ct = 0;

void dfs_bcc(int u, int p = -1)
{
    static int epoch = 0;
    dfn[u] = low[u] = epoch++;
    for (int w = head[u]; w != -1; w = next[w]) if (dest[w] != p) {
        if (dfn[dest[w]] == -1) {
            stk[top++] = w;
            dfs_bcc(dest[w], u);
            if (low[dest[w]] >= dfn[u]) {
                do bcc[bcc_ct].push_back(stk[--top]); while (stk[top] != w);
                ++bcc_ct;
            }
            low[u] = std::min(low[u], low[dest[w]]);
        } else if (dfn[dest[w]] < dfn[u]) {
            stk[top++] = w;
            low[u] = std::min(low[u], dfn[dest[w]]);
        }
    }
}

inline bool check_cycle(const std::vector<int> &block)
{
    std::set<int> s;
    for (int w : block) { s.insert(dest[w]); s.insert(dest[w ^ 1]); }
    return s.size() == block.size();
}

int main()
{
    preprocess();

    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < n; ++i) head[i] = -1;
    int u, v;
    for (int i = 0; i < m; ++i) {
        scanf("%d%d", &u, &v); --u, --v;
        add_edge(u, v);
        add_edge(v, u);
    }

    for (int i = 0; i < n; ++i) dfn[i] = -1;
    for (int i = 0; i < n; ++i) if (dfn[i] == -1) dfs_bcc(i, -1);

    int64 ans = 1;
    for (int i = 0; i < bcc_ct; ++i) {
        //for (int w : bcc[i]) printf(" %d-%d", dest[w], dest[w ^ 1]); putchar('\n');
        if (bcc[i].size() == 1u) {
            (ans *= k)__;
        } else if (check_cycle(bcc[i])) {
            int sz = bcc[i].size();
            int64 cur = 0;
            for (int i = 0; i < sz; ++i) cur += fpow(k, gcd(i, sz));
            (ans *= cur * fpow(sz, MODULUS - 2))__;
        } else {
            int sz = bcc[i].size();
            (ans *= binom(sz + k - 1, k - 1))__;
        }
    }
    printf("%lld\n", ans);

    return 0;
}

Submission Info

Submission Time
Task F - Painting Graphs with AtCoDeer
User cyand1317
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3092 Byte
Status WA
Exec Time 1 ms
Memory 256 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:79:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &k);
                                ^
./Main.cpp:83:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &u, &v); --u, --v;
                              ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1300
Status
AC × 3
AC × 55
WA × 9
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt, 1_042.txt, 1_043.txt, 1_044.txt, 1_045.txt, 1_046.txt, 1_047.txt, 1_048.txt, 1_049.txt, 1_050.txt, 1_051.txt, 1_052.txt, 1_053.txt, 1_054.txt, 1_055.txt, 1_056.txt, 1_057.txt, 1_058.txt, 1_059.txt, 1_060.txt, 1_061.txt, 1_062.txt, 1_063.txt
Case Name Status Exec Time Memory
0_000.txt AC 1 ms 256 KB
0_001.txt AC 1 ms 256 KB
0_002.txt AC 1 ms 256 KB
1_003.txt AC 1 ms 256 KB
1_004.txt AC 1 ms 256 KB
1_005.txt AC 1 ms 256 KB
1_006.txt AC 1 ms 256 KB
1_007.txt AC 1 ms 256 KB
1_008.txt AC 1 ms 256 KB
1_009.txt AC 1 ms 256 KB
1_010.txt AC 1 ms 256 KB
1_011.txt AC 1 ms 256 KB
1_012.txt AC 1 ms 256 KB
1_013.txt AC 1 ms 256 KB
1_014.txt WA 1 ms 256 KB
1_015.txt WA 1 ms 256 KB
1_016.txt AC 1 ms 256 KB
1_017.txt AC 1 ms 256 KB
1_018.txt WA 1 ms 256 KB
1_019.txt AC 1 ms 256 KB
1_020.txt WA 1 ms 256 KB
1_021.txt WA 1 ms 256 KB
1_022.txt WA 1 ms 256 KB
1_023.txt AC 1 ms 256 KB
1_024.txt AC 1 ms 256 KB
1_025.txt WA 1 ms 256 KB
1_026.txt AC 1 ms 256 KB
1_027.txt WA 1 ms 256 KB
1_028.txt AC 1 ms 256 KB
1_029.txt AC 1 ms 256 KB
1_030.txt AC 1 ms 256 KB
1_031.txt AC 1 ms 256 KB
1_032.txt AC 1 ms 256 KB
1_033.txt AC 1 ms 256 KB
1_034.txt AC 1 ms 256 KB
1_035.txt AC 1 ms 256 KB
1_036.txt AC 1 ms 256 KB
1_037.txt AC 1 ms 256 KB
1_038.txt AC 1 ms 256 KB
1_039.txt AC 1 ms 256 KB
1_040.txt AC 1 ms 256 KB
1_041.txt AC 1 ms 256 KB
1_042.txt AC 1 ms 256 KB
1_043.txt AC 1 ms 256 KB
1_044.txt AC 1 ms 256 KB
1_045.txt WA 1 ms 256 KB
1_046.txt AC 1 ms 256 KB
1_047.txt AC 1 ms 256 KB
1_048.txt AC 1 ms 256 KB
1_049.txt AC 1 ms 256 KB
1_050.txt AC 1 ms 256 KB
1_051.txt AC 1 ms 256 KB
1_052.txt AC 1 ms 256 KB
1_053.txt AC 1 ms 256 KB
1_054.txt AC 1 ms 256 KB
1_055.txt AC 1 ms 256 KB
1_056.txt AC 1 ms 256 KB
1_057.txt AC 1 ms 256 KB
1_058.txt AC 1 ms 256 KB
1_059.txt AC 1 ms 256 KB
1_060.txt AC 1 ms 256 KB
1_061.txt AC 1 ms 256 KB
1_062.txt AC 1 ms 256 KB
1_063.txt AC 1 ms 256 KB