Editorial - Toyota Programming Contest 2023#3（AtCoder Beginner Contest 306）

Contest Duration: 2023-06-17(Sat) 12:00 - 2023-06-17(Sat) 13:40 (local time) (100 minutes) Back to Home

Official

G - Return to 1 Editorial by en_translator

First of all, the vertices not reachable from vertex $1$ and those from which vertex $1$ is not reachable (and the adjacent edges) can be removed from the graph. We now assume that the graph is strongly connected.

Let $L$ be the set of sizes of lengths of cycles containing vertex $1$ , and $G$ be the greatest common divisors of the numbers contained in $L$ (or $0$ if $L$ is an empty set). Then, the answer is Yes if and only if $G$ is a divisor of $10^{10^{100}}$ .

Proof

Suppose that there are two cycles of lengths

a

and

b

. Also, suppose that

\gcd(a,b) = g

, where

a=ga'

and

b=gb'

. Then, for all integers

k\geq a'b'

, there exist non-negative integers

x

and

y

such that

a'x+b'y=k

. Thus, by using the two cycles together, we can construct any cycle of a length that is a multiple of

\gcd(a,b)

and is at least

\mathrm{lcm}(a,b)

. As an extension, by using

t

cycles of lengths

l_1,l_2, \dots

, and

l_t

, we can construct any cycle of a length that is a multiple of

\gcd(l_1,l_2, \dots l_t)

and is at least

\mathrm{lcm}(l_1,l_2, \dots l_t)

, which can be shown by induction. Since

10^{10^{100}}

is sufficiently large, if

G

is a divisor of

10^{10^{100}}

, then a cycle of length

10^{10^{100}}

exists. Conversely, if

G

has a prime divisor other than

2

and

5

, then it is obvious that there is no cycle of a length that is a multiple of

10^{10^{100}}

. Thus, the proposition is proven.

However, $L$ can be an infinite set, so we cannot find $G$ . Now, (it is a bit sudden) let us take an arbitrary directed spanning tree $T$ rooted at vertex $1$ , and let $d_i$ be the depth of vertex $i$ in $T$ . Then, for all integers $a$ , the following fact holds:

$L\text{ contains an integer that is }\textbf{not}\text{ a multiple of }L \Leftrightarrow \text{there is an edge }u\rightarrow v\text{ such that } d_u+1-d_v \not\equiv 0 \pmod a.$

Proof

( $\Rightarrow$ ) We show the contraposition. Since $d_u+1 \equiv d_v \pmod a$ for all edges $u \rightarrow v$ , the sequence of $d_i \bmod a$ on the cycle that starts from and ends at vertex $1$ is always periodic, like $0 \rightarrow 1 \rightarrow \dots \rightarrow a-1 \rightarrow 0 \rightarrow 1 \rightarrow \dots \rightarrow 0$ . Thus, $l \bmod a \equiv 0$ for all $l \in L$ .

( $\Leftarrow$ ) Take a cycle that contains an edge such that $d_u+1-d_v \not\equiv 0 \pmod a$ exactly once, and let $l \in L$ be its length. (Since every edge in $T$ satisfies $d_u+1-d_v =0\equiv 0 \pmod a$ , such a cycle always exists.) Then, $l \not\equiv 0 \pmod a$ .

Hence, if we let $G'$ be the greatest common divisor of $|d_u+1-d_v|$ for all edges $u \rightarrow v$ , then $G'$ coincides with $g$ . Since $G$ can be found in a total of $O(N+M)$ time, the problem has been solved.

Sample code (C++):

Copy

#include<bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> G(n), rG(n);
        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            --u, --v;
            G[u].push_back(v);
            rG[v].push_back(u);
        }
        vector<int> dep(n, -1);
        dep[0] = 0;
        auto dfs = [&](auto &dfs, int u) -> void {
            for (int v: G[u]) {
                if (dep[v] != -1) continue;
                dep[v] = dep[u] + 1;
                dfs(dfs, v);
            }
        };
        dfs(dfs, 0);
        vector<bool> valid(n); // valid[i] = i から 0 に到達可能かどうか
        auto dfs_r = [&](auto &dfs_r, int u) -> void {
            valid[u] = true;
            for (int v: rG[u]) {
                if (valid[v]) continue;
                dfs_r(dfs_r, v);
            }
        };
        dfs_r(dfs_r, 0);
        for (int i = 0; i < n; i++) if (!valid[i]) dep[i] = -1;
        int g = 0;
        for (int u = 0; u < n; u++) {
            if (dep[u] == -1) continue;
            for (int v: G[u]) {
                if (dep[v] == -1) continue;
                g = gcd(g, abs(dep[u] + 1 - dep[v]));
            }
        }
        if (!g) {
            cout << "No\n";
            continue;
        }
        while (g % 2 == 0) g /= 2;
        while (g % 5 == 0) g /= 5;
        cout << (g == 1 ? "Yes" : "No") << '\n';
    }
}

#include<bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> G(n), rG(n);
        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            --u, --v;
            G[u].push_back(v);
            rG[v].push_back(u);
        }
        vector<int> dep(n, -1);
        dep[0] = 0;
        auto dfs = [&](auto &dfs, int u) -> void {
            for (int v: G[u]) {
                if (dep[v] != -1) continue;
                dep[v] = dep[u] + 1;
                dfs(dfs, v);
            }
        };
        dfs(dfs, 0);
        vector<bool> valid(n); // valid[i] = i から 0 に到達可能かどうか
        auto dfs_r = [&](auto &dfs_r, int u) -> void {
            valid[u] = true;
            for (int v: rG[u]) {
                if (valid[v]) continue;
                dfs_r(dfs_r, v);
            }
        };
        dfs_r(dfs_r, 0);
        for (int i = 0; i < n; i++) if (!valid[i]) dep[i] = -1;
        int g = 0;
        for (int u = 0; u < n; u++) {
            if (dep[u] == -1) continue;
            for (int v: G[u]) {
                if (dep[v] == -1) continue;
                g = gcd(g, abs(dep[u] + 1 - dep[v]));
            }
        }
        if (!g) {
            cout << "No\n";
            continue;
        }
        while (g % 2 == 0) g /= 2;
        while (g % 5 == 0) g /= 5;
        cout << (g == 1 ? "Yes" : "No") << '\n';
    }
}

posted:
last update: