提出 #38804839

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast") // -Ofast 预编译优化

#define lp (p << 1)
#define rp ((p << 1)|1)
#define ll long long
#define ld long double
#define pb push_back
#define all(s) s.begin(), s.end()
#define sz(x) (int)(x).size()
#define fastio cin.tie(0) -> sync_with_stdio(0) 
#define pii pair<int, int>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define F(i, a, b) for(int i=(a); i <= (b); ++i)
#define SUM 1
#define MAX 0
#define fi first
#define se second
#define il inline
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define PQ(TYPE, FUNCTOR) priority_queue<TYPE, vector<TYPE>, FUNCTOR<TYPE>> 
#define HERE printf("HERE, __LINE__==%d\n", __LINE__);
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fll

template<typename T, T...>
struct myinteger_sequence { };

template<typename T, typename S1 = void, typename S2 = void>
struct helper{
    std::string operator()(const T& s){
        return std::string(s);
    }
}; 

template<typename T>
struct helper<T, decltype((void)std::to_string(std::declval<T>())), typename std::enable_if<!std::is_same<typename std::decay<T>::type, char>::value, void>::type>{
    std::string operator()(const T& s){
        return std::to_string(s);
    }
};

template<typename T>
struct helper<T, void, typename std::enable_if<std::is_same<typename std::decay<T>::type, char>::value, void>::type>{
    std::string operator()(const T& s){
        return std::string(1, s);
    }
};

template<typename T, typename S1 =void, typename S2 =void>
struct seqhelper{
    const static bool seq = false;
};

template<typename T>
struct seqhelper<T, decltype((void)(std::declval<T>().begin())), decltype((void)(std::declval<T>().end()))>{
    const static bool seq = !(std::is_same<typename std::decay<T>::type, std::string>::value);
};

template<std::size_t N, std::size_t... I>
struct gen_indices : gen_indices<(N - 1), (N - 1), I...> { };
template<std::size_t... I>
struct gen_indices<0, I...> : myinteger_sequence<std::size_t, I...> { };

template<typename T, typename REDUNDANT = void>
struct converter{
    template<typename H>
    std::string& to_string_impl(std::string& s, H&& h)
    {
        using std::to_string;
        s += converter<H>().convert(std::forward<H>(h));
        return s;    
    }

    template<typename H, typename... T1>
    std::string& to_string_impl(std::string& s, H&& h, T1&&... t)
    {
        using std::to_string;
        s += converter<H>().convert(std::forward<H>(h)) + ", ";
        return to_string_impl(s, std::forward<T1>(t)...);
    }

    template<typename... T1, std::size_t... I>
    std::string mystring(const std::tuple<T1...>& tup, myinteger_sequence<std::size_t, I...>)
    {
        std::string result;
        int ctx[] = { (to_string_impl(result, std::get<I>(tup)...), 0), 0 };
        (void)ctx;
        return result;
    }

    template<typename... S>
    std::string mystring(const std::tuple<S...>& tup)
    {
        return mystring(tup, gen_indices<sizeof...(S)>{});
    }

    template<typename S=T>
    std::string convert(const S& x){
        return helper<S>()(x);
    }

    template<typename... S>
    std::string convert(const std::tuple<S...>& tup){
        std::string res = std::move(mystring(tup));
        res = "{" + res + "}";
        return res;
    }

    template<typename S1, typename S2>
    std::string convert(const std::pair<S1, S2>& x){
        return "{" + converter<S1>().convert(x.first) + ", " + converter<S2>().convert(x.second) + "}";
    }
};

template<typename T>
struct converter<T, typename std::enable_if<seqhelper<T>::seq, void>::type>{
    template<typename S=T>
    std::string convert(const S& x){
        int len = 0;
        std::string ans = "{";
        for(auto it = x.begin(); it != x.end(); ++it){
            ans += move(converter<typename S::value_type>().convert(*it)) + ", ";
            ++len;
        }
        if(len == 0) return "{[EMPTY]}";
        ans.pop_back(), ans.pop_back();
        return ans + "}";
    }
};

template<typename T>
std::string luangao(const T& x){
    return converter<T>().convert(x);
}

//jiangly Codeforces
constexpr int P = 998244353;
using i64 = long long;
// assume -P <= x < 2P
int norm(int x) {
    if (x < 0) {
        x += P;
    }
    if (x >= P) {
        x -= P;
    }
    return x;
}
template<class T>
T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    Z(i64 x) : x(norm((int)(x % P))) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(P - x));
    }
    Z inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = i64(x) * rhs.x % P;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        i64 v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};

template<typename T>
vector<pair<T, T>> factorize(T x){
    vector<pair<T, T>> primes;
    for (T p = 2; p * p <= x; ++p) {
        if (x % p == 0) {
            T k = 1;
            for (x /= p; x % p == 0; x /= p) ++k;
            primes.push_back({p, k});
        }
    }
    if (x > T(1)) primes.push_back({x, T(1)});
    return primes;
}

template<typename T>
void facmap(T x, map<T, T>& primes){
    for (T p = 2; p * p <= x; ++p) {
        if (x % p == 0) {
            T k = 1;
            for (x /= p; x % p == 0; x /= p) ++k;
            primes[p] += k;
        }
    }
    if (x > T(1)) primes[x] += T(1);
}

ll intsqrt (ll x) {
    ll ans = 0;
    for (ll k = 1LL << 30; k != 0; k /= 2) {
        if ((ans + k) * (ans + k) <= x) {
            ans += k;
        }
    }
    return ans;
}


template<typename T>
T gcd(ll x, T y) {
    if (!y) return x;
    return gcd(y, x % y);
}

template<typename T>
T exgcd(T a, T b, T &x, T &y) {//exgcd 求逆元
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }
    
    T re = exgcd(b, a % b, y, x);
    y -= x * (a / b);
    return re;
}


#define DEBUG 0
#define SINGLE 0

void debug(const char* p){
    #if DEBUG
    freopen(p, "r", stdin); 
    #else
    fastio;
    #endif      
}

#define C 2005
int c[C];
vector<int> out[C];
vector<int> vis[C];
int n, m;

struct dis{
    int x, y, d;
};

int bfs(int x, int y, int tx, int ty){
    queue<dis> q;
    vis[x][y] = 1;
    q.push(dis{x, y, 0});
    while(!q.empty()){
        auto t = q.front();
        q.pop();
        int i = t.x, j = t.y, l = t.d;
        if(i == tx && j == ty){
            return l;
        }
        for(int ni: out[i]){
            for(int nj: out[j]){
                if(c[ni] != c[nj] && !vis[ni][nj]){
                    q.push(dis{ni, nj, l+1});
                    vis[ni][nj] = 1;
                }
            }
        }
    }
    return -1;
}

void solve(int test){
    cin >> n >> m;
    F(i, 1, n) {
        cin >> c[i];
        out[i].clear();
        vis[i].clear();
        vis[i].resize(n+1);
        F(j, 1, n){
            vis[i][j] = 0;
        }
    }
    F(i, 1, m){
        int ui, vi;
        cin >> ui >> vi;
        out[ui].pb(vi);
        out[vi].pb(ui);
    }
    int res = bfs(1, n, n, 1);
    cout << res << "\n";
}


signed main(int argc, char** argv){
    debug(argc==1?"test1.txt":argv[1]);
    int t = 1;
    int test = 0;
    #if !SINGLE
    cin >> t;
    #endif
    while(t--){
        solve(test++);
    }
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘void debug(const char*)’:
./Main.cpp:284:24: warning: unused parameter ‘p’ [-Wunused-parameter]
  284 | void debug(const char* p){
      |            ~~~~~~~~~~~~^
./Main.cpp: In function ‘void solve(int)’:
./Main.cpp:325:16: warning: unused parameter ‘test’ [-Wunused-parameter]
  325 | void solve(int test){
      |            ~~~~^~~~

ジャッジ結果