#655899 (C++17) No.186 中華風 (Easy)

提出ソース

結果

問題	No.186 中華風 (Easy)
ユーザー	nanophoto12
提出日時	2021-05-09 21:57:25
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	8,677 bytes
コンパイル時間	4,664 ms
コンパイル使用メモリ	265,228 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-09-19 02:45:50
合計ジャッジ時間	5,651 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	WA	-
testcase_17	WA	-
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	2 ms 5,376 KB
testcase_22	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;

#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)

template<typename T>
void chmax(T& reference, T value) {
	reference = max(reference, value);
}

template<typename T>
void chmaxmap(map<T, T>& m, T key, T value) {
	if (m.count(key)) {
		chmax(m[key], value);
	}
	else {
		m[key] = value;
	}
}

template<typename T>
void chmin(T& reference, T value) {
	reference = min(reference, value);
}

template< typename G >
struct HeavyLightDecomposition {
    G& g;
    vector< int > sz, in, out, head, rev, par;

    HeavyLightDecomposition(G& g) :
        g(g), sz(g.size()), in(g.size()), out(g.size()), head(g.size()), rev(g.size()), par(g.size()) {}

    void dfs_sz(int idx, int p) {
        par[idx] = p;
        sz[idx] = 1;
        if (g[idx].size() && g[idx][0] == p) swap(g[idx][0], g[idx].back());
        for (auto& to : g[idx]) {
            if (to == p) continue;
            dfs_sz(to, idx);
            sz[idx] += sz[to];
            if (sz[g[idx][0]] < sz[to]) swap(g[idx][0], to);
        }
    }

    void dfs_hld(int idx, int par, int& times) {
        in[idx] = times++;
        rev[in[idx]] = idx;
        for (auto& to : g[idx]) {
            if (to == par) continue;
            head[to] = (g[idx][0] == to ? head[idx] : to);
            dfs_hld(to, idx, times);
        }
        out[idx] = times;
    }

    void build() {
        dfs_sz(0, -1);
        int t = 0;
        dfs_hld(0, -1, t);
    }

    int la(int v, int k) {
        while (1) {
            int u = head[v];
            if (in[v] - k >= in[u]) return rev[in[v] - k];
            k -= in[v] - in[u] + 1;
            v = par[u];
        }
    }

    int lca(int u, int v) {
        for (;; v = par[head[v]]) {
            if (in[u] > in[v]) swap(u, v);
            if (head[u] == head[v]) return u;
        }
    }

    template< typename T, typename Q, typename F >
    T query(int u, int v, const T& ti, const Q& q, const F& f, bool edge = false) {
        T l = ti, r = ti;
        for (;; v = par[head[v]]) {
            if (in[u] > in[v]) swap(u, v), swap(l, r);
            if (head[u] == head[v]) break;
            l = f(q(in[head[v]], in[v] + 1), l);
        }
        return f(f(q(in[u] + edge, in[v] + 1), l), r);
    }

    template< typename Q >
    void add(int u, int v, const Q& q, bool edge = false) {
        for (;; v = par[head[v]]) {
            if (in[u] > in[v]) swap(u, v);
            if (head[u] == head[v]) break;
            q(in[head[v]], in[v] + 1);
        }
        q(in[u] + edge, in[v] + 1);
    }
};

typedef vector<vector<int>> UnWeightedGraph;

class lca {
public:
    typedef vector<vector<int>> Graph;
    const int n;
    const int log2_n;
    std::vector<std::vector<int>> parent;
    std::vector<int> depth;

    lca(const Graph& g, int root)
        : n(g.size()), log2_n(log2(n) + 1), parent(log2_n, std::vector<int>(n)), depth(n) {
        dfs(g, root, -1, 0);
        for (int k = 0; k + 1 < log2_n; k++) {
            for (int v = 0; v < (int)g.size(); v++) {
                if (parent[k][v] < 0)
                    parent[k + 1][v] = -1;
                else
                    parent[k + 1][v] = parent[k][parent[k][v]];
            }
        }
    }

    void dfs(const Graph& g, int v, int p, int d) {
        parent[0][v] = p;
        depth[v] = d;
        for (int j = 0; j < g[v].size(); j++) {
            if (g[v][j] != p) dfs(g, g[v][j], v, d + 1);
        }
    }

    int get(int u, int v) {
        if (depth[u] > depth[v]) std::swap(u, v);
        for (int k = 0; k < log2_n; k++) {
            if ((depth[v] - depth[u]) >> k & 1) {
                v = parent[k][v];
            }
        }
        if (u == v) return u;
        for (int k = log2_n - 1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }

    int dist(int u, int v) {
        return depth[u] + depth[v] - 2 * depth[get(u, v)];
    }

};

namespace {
    using namespace std;

    template< typename G >
    struct LowLink {
        const G& g;
        vector< int > used, ord, low;
        vector< int > articulation;
        vector< pair< int, int > > bridge;

        LowLink(const G& g) : g(g) {}

        int dfs(int idx, int k, int par) {
            used[idx] = true;
            ord[idx] = k++;
            low[idx] = ord[idx];
            bool is_articulation = false;
            int cnt = 0;
            for (auto& to : g[idx]) {
                if (!used[to]) {
                    ++cnt;
                    k = dfs(to, k, idx);
                    low[idx] = min(low[idx], low[to]);
                    is_articulation |= ~par && low[to] >= ord[idx];
                    if (ord[idx] < low[to]) bridge.emplace_back(minmax(idx, (int)to));
                }
                else if (to != par) {
                    low[idx] = min(low[idx], ord[to]);
                }
            }
            is_articulation |= par == -1 && cnt > 1;
            if (is_articulation) articulation.push_back(idx);
            return k;
        }

        virtual void build() {
            used.assign(g.size(), 0);
            ord.assign(g.size(), 0);
            low.assign(g.size(), 0);
            int k = 0;
            for (int i = 0; i < g.size(); i++) {
                if (!used[i]) k = dfs(i, k, -1);
            }
        }
    };

    template< typename G >
    struct TwoEdgeConnectedComponents {
        vector< int > comp;
        LowLink< G > lowLink_;
        TwoEdgeConnectedComponents(const G& g) : lowLink_(g) {}

        int operator[](const int& k) {
            return comp[k];
        }

        void dfs(int idx, int par, int& k) {
            if (~par && lowLink_.ord[par] >= lowLink_.low[idx]) comp[idx] = comp[par];
            else comp[idx] = k++;
            for (auto& to : lowLink_.g[idx]) {
                if (comp[to] == -1) dfs(to, idx, k);
            }
        }

        typedef std::vector<std::vector<int>> UnWeightedGraph;

        void build(UnWeightedGraph& t) {
            lowLink_.build();
            comp.assign(lowLink_.g.size(), -1);
            int k = 0;
            for (int i = 0; i < comp.size(); i++) {
                if (comp[i] == -1) dfs(i, -1, k);
            }
            t.resize(k);
            for (auto& e : lowLink_.bridge) {
                int x = comp[e.first], y = comp[e.second];
                t[x].push_back(y);
                t[y].push_back(x);
            }
        }
    };
}

class Primes {
public:
    vector<int> Prime_Number;
    vector<bool> is_prime_;
    Primes(int N) {
        is_prime_.resize(N + 1, true);
        is_prime_[0] = is_prime_[1] = false;
        for (int i = 0; i < N + 1; i++) {
            if (is_prime_[i]) {
                Prime_Number.push_back(i);
                for (int j = 2 * i; j <= N; j += i) is_prime_[j] = false;
            }
        }
    }
    int operator[](int i) { return Prime_Number[i]; }
    int size() { return Prime_Number.size(); }
    int back() { return Prime_Number.back(); }
    bool isPrime(int q) { return is_prime_[q]; }
};

int digits(ll v) {
    int c = 0;
    while (v) {
        v /= 10;
        c++;
    }
    return c;
}

ll gcd(ll a, ll b) { while (b) a %= b, swap(a, b); return abs(a); }

ll divide(ll n, ll v) {
    ll c = 0;
    while (n % v == 0) {
        n /= v;
        c++;
    }
    return c;
}

#include <atcoder/all>

using namespace atcoder;

struct edge_ {
    ll from;
    ll to;
    ll len;
};

void solve(ll r) {
    int n = 0;
    ll pr = r;
    while (pr) {
        n++;
        pr /= 2;
    }
    vector<edge_> g;
    for (ll i = 0; i < n-1; i++) {
        g.push_back({ i+1, i+2, 0 });
        ll length = 1LL << i;
        g.push_back({ i+1, i+2, length });
    }
    ll bits = 1LL << (n - 1);
    for (int i = n-2; i >= 0; i--) {
        ll c = 1LL << i;
        if (r >> i & 1) {
            g.push_back({ i+1 , n, bits });
            bits += 1LL << i;
        }
    }
    cout << n << " " << g.size() << endl;
    for (auto e : g) {
        cout << e.from << " " << e.to << " " << e.len << endl;
    }
}

typedef modint1000000007 mint;

int main() {
    vector<ll> x(3), y(3);
    rep(i, 3) {
        cin >> x[i] >> y[i];
    }
    auto c = atcoder::crt(x, y);
    if (c == P{0, 0}) {
        cout << -1 << endl;
        return 0;
    }
    cout << c.first << endl;
    return 0;
}

yukicoder

結果

テストケース

ソースコード