JOI'22 二次予選

A.cpp

/** //
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
/* */

#include <bits/stdc++.h>

/** */ // ACL
#include <atcoder/all>
using namespace atcoder;
// ACL END */

/** / // Boost BigInteger
#include <boost/multiprecision/cpp_int.hpp>
using bint = boost::multiprecision::cpp_int;
// Boost BigInteger END*/

#define int LL
#define stoi stoll

#define override_rep(i, l, r, mes, ...) mes
#define rep1(i, n) for (int i = 0; i < n; i++)
#define rep2(i, l, r) for (int i = l; i < r; i++)
#define rep(...) override_rep(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)

using namespace std;

using LL = long long;
using LD = double;
using P = std::pair<int, int>;
using mi = modint998244353;
constexpr int MOD = 1e9 + 7;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

template<typename T>
using greater_pqueue = priority_queue<T, vector<T>, greater<>>;

template<typename T, typename U>
inline bool chmin(T& a, U b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U>
inline bool chmax(T& a, U b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U>
inline std::istream& operator>>(std::istream& in, std::pair<T, U>& p) {
    in >> p.first >> p.second;
    return in;
}
template<typename T>
int binarySearch(int ng, int ok, T isOK) {
    while (std::abs(ok - ng) > 1) {
        int mid = (ok + ng) / 2;
        if (isOK(mid))
            ok = mid;
        else
            ng = mid;
    }
    return ok;
}
template<typename T>
std::map<T, int> compress(std::vector<T>& base_list) {
    std::sort(base_list.begin(), base_list.end());
    base_list.erase(std::unique(base_list.begin(), base_list.end()), base_list.end());
    std::map<T, int> ret;
    rep(i, base_list.size()) {
        ret[base_list[i]] = i;
    }
    return ret;
}
std::vector<int> topologicalSort(const std::vector<std::vector<int>>& graph, bool& flag) {
    std::vector<int> memo(graph.size(), 0);
    for (const auto& vec : graph) {
        for (auto it : vec) {
            memo[it]++;
        }
    }
    std::vector<int> ret(graph.size());

    int cnt = 0, bcnt = 0;
    for (int i = 0; i < graph.size(); i++) {
        if (memo[i] == 0) ret[cnt++] = i;
    }
    if (bcnt + 1 < cnt) flag = true;
    bcnt = cnt;

    for (int i = 0; i < graph.size(); i++) {
        for (auto it : graph[ret[i]]) {
            memo[it]--;
            if (memo[it] == 0) {
                ret[cnt++] = it;
            }
        }
        if (bcnt + 1 < cnt) flag = true;
        bcnt = cnt;
    }

    return ret;
}
std::vector<int> makeDivisors(int n) {
    std::vector<int> re;
    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            re.push_back(i);
            if (i != n / i) re.push_back(n / i);
        }
    }
    return re;
}

class HeavyLightDecomposition {
  public:
    std::vector<std::vector<int>> g;
    int n, t;
    std::vector<int> sz, in, nxt, out, parent, depth;
    void dfs_sz(int v, int par) {
        sz[v] = 1;
        for (auto& u : g[v])
            if (u != par) {
                dfs_sz(u, v);
                sz[v] += sz[u];
                if (g[v][0] == par || sz[u] > sz[g[v][0]]) {
                    std::swap(u, g[v][0]);
                }
            }
    }

    void dfs_hld(int v, int par) {
        in[v] = t++;
        for (auto u : g[v])
            if (u != par) {
                nxt[u] = (u == g[v][0] ? nxt[v] : u);
                parent[u] = (u == g[v][0] ? parent[v] : v);
                depth[u] = (u == g[v][0] ? depth[v] : depth[v] + 1);
                dfs_hld(u, v);
            }
        out[v] = t;
    }

  public:
    HeavyLightDecomposition(const std::vector<std::vector<int>>& g) : g(g), n(g.size()), t(0), sz(n), in(n), nxt(n), out(n), parent(n), depth(n) {
        depth[0] = 0;
        dfs_sz(0, -1);
        dfs_hld(0, -1);
    }
};
template<typename T>
class BIT {
    std::vector<T> dat;
    int siz;

  public:
    BIT() = default;
    BIT(int siz) : siz(siz), dat(siz + 1, 0) {}
    T sum(int i) {
        T s = 0;
        while (i > 0) {
            s += dat[i];
            i -= i & -i;
        }
        return s;
    }
    void add(int i, T x) {
        while (i <= siz) {
            dat[i] += x;
            i += i & -i;
        }
    }
};
struct IoInit {
    IoInit() {
        std::cin.tie(nullptr);
        std::cout.tie(nullptr);
        std::ios::sync_with_stdio(false);
        std::cout << std::fixed << std::setprecision(16);
    }
} io_init;

signed main() {
    int q;
    cin>>q;
    stack<string> st;
    rep(i,q){
        string s;
        cin>>s;
        if(s=="READ"){
            cout<<st.top()<<endl;
            st.pop();
        }
        else{
            st.push(s);
        }
    }
}

B.cpp

/** //
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
/* */

#include <bits/stdc++.h>

/** */ // ACL
#include <atcoder/all>
using namespace atcoder;
// ACL END */

/** / // Boost BigInteger
#include <boost/multiprecision/cpp_int.hpp>
using bint = boost::multiprecision::cpp_int;
// Boost BigInteger END*/

#define int LL
#define stoi stoll

#define override_rep(i, l, r, mes, ...) mes
#define rep1(i, n) for (int i = 0; i < n; i++)
#define rep2(i, l, r) for (int i = l; i < r; i++)
#define rep(...) override_rep(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)

using namespace std;

using LL = long long;
using LD = double;
using P = std::pair<int, int>;
using mi = modint998244353;
constexpr int MOD = 1e9 + 7;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

template<typename T>
using greater_pqueue = priority_queue<T, vector<T>, greater<>>;

template<typename T, typename U>
inline bool chmin(T& a, U b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U>
inline bool chmax(T& a, U b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U>
inline std::istream& operator>>(std::istream& in, std::pair<T, U>& p) {
    in >> p.first >> p.second;
    return in;
}
template<typename T>
int binarySearch(int ng, int ok, T isOK) {
    while (std::abs(ok - ng) > 1) {
        int mid = (ok + ng) / 2;
        if (isOK(mid))
            ok = mid;
        else
            ng = mid;
    }
    return ok;
}
template<typename T>
std::map<T, int> compress(std::vector<T>& base_list) {
    std::sort(base_list.begin(), base_list.end());
    base_list.erase(std::unique(base_list.begin(), base_list.end()), base_list.end());
    std::map<T, int> ret;
    rep(i, base_list.size()) {
        ret[base_list[i]] = i;
    }
    return ret;
}
std::vector<int> topologicalSort(const std::vector<std::vector<int>>& graph, bool& flag) {
    std::vector<int> memo(graph.size(), 0);
    for (const auto& vec : graph) {
        for (auto it : vec) {
            memo[it]++;
        }
    }
    std::vector<int> ret(graph.size());

    int cnt = 0, bcnt = 0;
    for (int i = 0; i < graph.size(); i++) {
        if (memo[i] == 0) ret[cnt++] = i;
    }
    if (bcnt + 1 < cnt) flag = true;
    bcnt = cnt;

    for (int i = 0; i < graph.size(); i++) {
        for (auto it : graph[ret[i]]) {
            memo[it]--;
            if (memo[it] == 0) {
                ret[cnt++] = it;
            }
        }
        if (bcnt + 1 < cnt) flag = true;
        bcnt = cnt;
    }

    return ret;
}
std::vector<int> makeDivisors(int n) {
    std::vector<int> re;
    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            re.push_back(i);
            if (i != n / i) re.push_back(n / i);
        }
    }
    return re;
}

class HeavyLightDecomposition {
  public:
    std::vector<std::vector<int>> g;
    int n, t;
    std::vector<int> sz, in, nxt, out, parent, depth;
    void dfs_sz(int v, int par) {
        sz[v] = 1;
        for (auto& u : g[v])
            if (u != par) {
                dfs_sz(u, v);
                sz[v] += sz[u];
                if (g[v][0] == par || sz[u] > sz[g[v][0]]) {
                    std::swap(u, g[v][0]);
                }
            }
    }

    void dfs_hld(int v, int par) {
        in[v] = t++;
        for (auto u : g[v])
            if (u != par) {
                nxt[u] = (u == g[v][0] ? nxt[v] : u);
                parent[u] = (u == g[v][0] ? parent[v] : v);
                depth[u] = (u == g[v][0] ? depth[v] : depth[v] + 1);
                dfs_hld(u, v);
            }
        out[v] = t;
    }

  public:
    HeavyLightDecomposition(const std::vector<std::vector<int>>& g) : g(g), n(g.size()), t(0), sz(n), in(n), nxt(n), out(n), parent(n), depth(n) {
        depth[0] = 0;
        dfs_sz(0, -1);
        dfs_hld(0, -1);
    }
};
template<typename T>
class BIT {
    std::vector<T> dat;
    int siz;

  public:
    BIT() = default;
    BIT(int siz) : siz(siz), dat(siz + 1, 0) {}
    T sum(int i) {
        T s = 0;
        while (i > 0) {
            s += dat[i];
            i -= i & -i;
        }
        return s;
    }
    void add(int i, T x) {
        while (i <= siz) {
            dat[i] += x;
            i += i & -i;
        }
    }
};
struct IoInit {
    IoInit() {
        std::cin.tie(nullptr);
        std::cout.tie(nullptr);
        std::ios::sync_with_stdio(false);
        std::cout << std::fixed << std::setprecision(16);
    }
} io_init;

signed main() {
    int h,w;
    cin>>h>>w;
    vector<string> s(h);
    rep(i,h)cin>>s[i];
    vector dist(h,vector(w,LLONG_MAX));
    queue<tuple<int,int,int>> que;
    dist[0][0]=0;
    que.emplace(0,0,0);
    while(!que.empty()){
        auto [x,y,di]=que.front();que.pop();
        if(x==h-1&&y==w-1){
            cout<<di<<endl;
            return 0;
        }
        rep(i,4){
            int nx=x+dx[i],ny=y+dy[i];
            if(nx<0||ny<0||h<=nx||w<=ny)continue;
            if(s[x][y]!=s[nx][ny]&&di+1<dist[nx][ny]){
                dist[nx][ny]=di+1;
                que.emplace(nx,ny,di+1);
            }
        }
    }
    cout<<-1<<endl;
}

C.cpp

/** //
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
/* */

#include <bits/stdc++.h>

/** */ // ACL
#include <atcoder/all>
using namespace atcoder;
// ACL END */

/** / // Boost BigInteger
#include <boost/multiprecision/cpp_int.hpp>
using bint = boost::multiprecision::cpp_int;
// Boost BigInteger END*/

#define int LL
#define stoi stoll

#define override_rep(i, l, r, mes, ...) mes
#define rep1(i, n) for (int i = 0; i < n; i++)
#define rep2(i, l, r) for (int i = l; i < r; i++)
#define rep(...) override_rep(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)

using namespace std;

using LL = long long;
using LD = double;
using P = std::pair<int, int>;
using mi = modint998244353;
constexpr int MOD = 1e9 + 7;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

template<typename T>
using greater_pqueue = priority_queue<T, vector<T>, greater<>>;

template<typename T, typename U>
inline bool chmin(T& a, U b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U>
inline bool chmax(T& a, U b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U>
inline std::istream& operator>>(std::istream& in, std::pair<T, U>& p) {
    in >> p.first >> p.second;
    return in;
}
template<typename T>
int binarySearch(int ng, int ok, T isOK) {
    while (std::abs(ok - ng) > 1) {
        int mid = (ok + ng) / 2;
        if (isOK(mid))
            ok = mid;
        else
            ng = mid;
    }
    return ok;
}
template<typename T>
std::map<T, int> compress(std::vector<T>& base_list) {
    std::sort(base_list.begin(), base_list.end());
    base_list.erase(std::unique(base_list.begin(), base_list.end()), base_list.end());
    std::map<T, int> ret;
    rep(i, base_list.size()) {
        ret[base_list[i]] = i;
    }
    return ret;
}
std::vector<int> topologicalSort(const std::vector<std::vector<int>>& graph, bool& flag) {
    std::vector<int> memo(graph.size(), 0);
    for (const auto& vec : graph) {
        for (auto it : vec) {
            memo[it]++;
        }
    }
    std::vector<int> ret(graph.size());

    int cnt = 0, bcnt = 0;
    for (int i = 0; i < graph.size(); i++) {
        if (memo[i] == 0) ret[cnt++] = i;
    }
    if (bcnt + 1 < cnt) flag = true;
    bcnt = cnt;

    for (int i = 0; i < graph.size(); i++) {
        for (auto it : graph[ret[i]]) {
            memo[it]--;
            if (memo[it] == 0) {
                ret[cnt++] = it;
            }
        }
        if (bcnt + 1 < cnt) flag = true;
        bcnt = cnt;
    }

    return ret;
}
std::vector<int> makeDivisors(int n) {
    std::vector<int> re;
    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            re.push_back(i);
            if (i != n / i) re.push_back(n / i);
        }
    }
    return re;
}

class HeavyLightDecomposition {
  public:
    std::vector<std::vector<int>> g;
    int n, t;
    std::vector<int> sz, in, nxt, out, parent, depth;
    void dfs_sz(int v, int par) {
        sz[v] = 1;
        for (auto& u : g[v])
            if (u != par) {
                dfs_sz(u, v);
                sz[v] += sz[u];
                if (g[v][0] == par || sz[u] > sz[g[v][0]]) {
                    std::swap(u, g[v][0]);
                }
            }
    }

    void dfs_hld(int v, int par) {
        in[v] = t++;
        for (auto u : g[v])
            if (u != par) {
                nxt[u] = (u == g[v][0] ? nxt[v] : u);
                parent[u] = (u == g[v][0] ? parent[v] : v);
                depth[u] = (u == g[v][0] ? depth[v] : depth[v] + 1);
                dfs_hld(u, v);
            }
        out[v] = t;
    }

  public:
    HeavyLightDecomposition(const std::vector<std::vector<int>>& g) : g(g), n(g.size()), t(0), sz(n), in(n), nxt(n), out(n), parent(n), depth(n) {
        depth[0] = 0;
        dfs_sz(0, -1);
        dfs_hld(0, -1);
    }
};
template<typename T>
class BIT {
    std::vector<T> dat;
    int siz;

  public:
    BIT() = default;
    BIT(int siz) : siz(siz), dat(siz + 1, 0) {}
    T sum(int i) {
        T s = 0;
        while (i > 0) {
            s += dat[i];
            i -= i & -i;
        }
        return s;
    }
    void add(int i, T x) {
        while (i <= siz) {
            dat[i] += x;
            i += i & -i;
        }
    }
};
struct IoInit {
    IoInit() {
        std::cin.tie(nullptr);
        std::cout.tie(nullptr);
        std::ios::sync_with_stdio(false);
        std::cout << std::fixed << std::setprecision(16);
    }
} io_init;

signed main() {
    int h, w;
    cin >> h >> w;
    vector a(h, vector(w, 0ll));
    vector ah(h,0ll),aw(w,0ll);
    rep(i, h) {
        rep(j, w) {
            cin >> a[i][j];
            ah[i]+=a[i][j];
            aw[j]+=a[i][j];
        }
    }
    int cnt=0;
    vector<vector<int>> hl,wl;
    rep(i,h){
        cnt+=ah[i];
        vector<int> tmp;
        tmp.push_back(0);
        int t=0;
        rep(j,h){
            t+=ah[j];
            if(t==cnt){
                tmp.push_back(j+1);
                t=0;
            }
            else if(t>cnt){
                goto joi;
            }
        }
        if(t!=0)goto joi;
        hl.push_back(tmp);
        joi:;
    }
    cnt=0;
    rep(i,w){
        cnt+=aw[i];
        vector<int> tmp;
        tmp.push_back(0);
        int t=0;
        rep(j,w){
            t+=aw[j];
            if(t==cnt){
                tmp.push_back(j+1);
                t=0;
            }
            else if(t>cnt){
                goto ioi;
            }
        }
        if(t!=0)goto ioi;
        wl.push_back(tmp);
    ioi:;
    }

    int ans=0;
    for(auto il:hl){
        for(auto jl:wl){
            int memo=-1;
            rep(i,il.size()-1){
                rep(j,jl.size()-1){
                    int c=0;
                    rep(x,il[i],il[i+1]){
                        rep(y,jl[j],jl[j+1]){
                            c+=a[x][y];
                        }
                    }
                    if(i==0&&j==0){
                        memo=c;
                    }
                    else if(memo!=c){
                        goto joiho;
                    }
                }
            }
            ans++;
            joiho:;
        }
    }
    cout<<ans-1<<endl;
}

D.cpp

/** //
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
/* */

#include <bits/stdc++.h>

/** */ // ACL
#include <atcoder/all>
using namespace atcoder;
// ACL END */

/** / // Boost BigInteger
#include <boost/multiprecision/cpp_int.hpp>
using bint = boost::multiprecision::cpp_int;
// Boost BigInteger END*/

#define int LL
#define stoi stoll

#define override_rep(i, l, r, mes, ...) mes
#define rep1(i, n) for (int i = 0; i < n; i++)
#define rep2(i, l, r) for (int i = l; i < r; i++)
#define rep(...) override_rep(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)

using namespace std;

using LL = long long;
using LD = double;
using P = std::pair<int, int>;
using mi = modint998244353;
constexpr int MOD = 1e9 + 7;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

template<typename T>
using greater_pqueue = priority_queue<T, vector<T>, greater<>>;

template<typename T, typename U>
inline bool chmin(T& a, U b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U>
inline bool chmax(T& a, U b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U>
inline std::istream& operator>>(std::istream& in, std::pair<T, U>& p) {
    in >> p.first >> p.second;
    return in;
}
template<typename T>
int binarySearch(int ng, int ok, T isOK) {
    while (std::abs(ok - ng) > 1) {
        int mid = (ok + ng) / 2;
        if (isOK(mid))
            ok = mid;
        else
            ng = mid;
    }
    return ok;
}
template<typename T>
std::map<T, int> compress(std::vector<T>& base_list) {
    std::sort(base_list.begin(), base_list.end());
    base_list.erase(std::unique(base_list.begin(), base_list.end()), base_list.end());
    std::map<T, int> ret;
    rep(i, base_list.size()) {
        ret[base_list[i]] = i;
    }
    return ret;
}
std::vector<int> topologicalSort(const std::vector<std::vector<int>>& graph, bool& flag) {
    std::vector<int> memo(graph.size(), 0);
    for (const auto& vec : graph) {
        for (auto it : vec) {
            memo[it]++;
        }
    }
    std::vector<int> ret(graph.size());

    int cnt = 0, bcnt = 0;
    for (int i = 0; i < graph.size(); i++) {
        if (memo[i] == 0) ret[cnt++] = i;
    }
    if (bcnt + 1 < cnt) flag = true;
    bcnt = cnt;

    for (int i = 0; i < graph.size(); i++) {
        for (auto it : graph[ret[i]]) {
            memo[it]--;
            if (memo[it] == 0) {
                ret[cnt++] = it;
            }
        }
        if (bcnt + 1 < cnt) flag = true;
        bcnt = cnt;
    }

    return ret;
}
std::vector<int> makeDivisors(int n) {
    std::vector<int> re;
    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            re.push_back(i);
            if (i != n / i) re.push_back(n / i);
        }
    }
    return re;
}

class HeavyLightDecomposition {
  public:
    std::vector<std::vector<int>> g;
    int n, t;
    std::vector<int> sz, in, nxt, out, parent, depth;
    void dfs_sz(int v, int par) {
        sz[v] = 1;
        for (auto& u : g[v])
            if (u != par) {
                dfs_sz(u, v);
                sz[v] += sz[u];
                if (g[v][0] == par || sz[u] > sz[g[v][0]]) {
                    std::swap(u, g[v][0]);
                }
            }
    }

    void dfs_hld(int v, int par) {
        in[v] = t++;
        for (auto u : g[v])
            if (u != par) {
                nxt[u] = (u == g[v][0] ? nxt[v] : u);
                parent[u] = (u == g[v][0] ? parent[v] : v);
                depth[u] = (u == g[v][0] ? depth[v] : depth[v] + 1);
                dfs_hld(u, v);
            }
        out[v] = t;
    }

  public:
    HeavyLightDecomposition(const std::vector<std::vector<int>>& g) : g(g), n(g.size()), t(0), sz(n), in(n), nxt(n), out(n), parent(n), depth(n) {
        depth[0] = 0;
        dfs_sz(0, -1);
        dfs_hld(0, -1);
    }
};
template<typename T>
class BIT {
    std::vector<T> dat;
    int siz;

  public:
    BIT() = default;
    BIT(int siz) : siz(siz), dat(siz + 1, 0) {}
    T sum(int i) {
        T s = 0;
        while (i > 0) {
            s += dat[i];
            i -= i & -i;
        }
        return s;
    }
    void add(int i, T x) {
        while (i <= siz) {
            dat[i] += x;
            i += i & -i;
        }
    }
};
struct IoInit {
    IoInit() {
        std::cin.tie(nullptr);
        std::cout.tie(nullptr);
        std::ios::sync_with_stdio(false);
        std::cout << std::fixed << std::setprecision(16);
    }
} io_init;

signed main() {
    int n,k;
    cin>>n>>k;
    vector<int> a(n);
    rep(i,n)cin>>a[i];
    vector<vector<int>> dp(n,vector<int>(n,0ll));
    rep(i,n){
        rep(j,i){
            dp[j][i]=a[i]+a[j];
        }
    }
    rep(i,1,n){
        int memo=a[i];
        rep(j,i-k+1){
            chmax(memo,dp[j][i]);
        }
        rep(j,i+1,n){
            if(0<=j-k&&j-k<i){
                chmax(memo,dp[j-k][i]);
            }
            dp[i][j]=memo+a[j];
        }
    }
    int mx=0;
    rep(i,n){
        rep(j,i){
            chmax(mx,dp[j][i]);
        }
    }
    cout<<mx<<endl;
}

E.cpp

/** //
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
/* */

#include <bits/stdc++.h>

/** */ // ACL
#include <atcoder/all>
using namespace atcoder;
// ACL END */

/** / // Boost BigInteger
#include <boost/multiprecision/cpp_int.hpp>
using bint = boost::multiprecision::cpp_int;
// Boost BigInteger END*/

#define int LL
#define stoi stoll

#define override_rep(i, l, r, mes, ...) mes
#define rep1(i, n) for (int i = 0; i < n; i++)
#define rep2(i, l, r) for (int i = l; i < r; i++)
#define rep(...) override_rep(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)

using namespace std;

using LL = long long;
using LD = double;
using P = std::pair<int, int>;
using mi = modint998244353;
constexpr int MOD = 1e9 + 7;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

template<typename T>
using greater_pqueue = priority_queue<T, vector<T>, greater<>>;

template<typename T, typename U>
inline bool chmin(T& a, U b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U>
inline bool chmax(T& a, U b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U>
inline std::istream& operator>>(std::istream& in, std::pair<T, U>& p) {
    in >> p.first >> p.second;
    return in;
}
template<typename T>
int binarySearch(int ng, int ok, T isOK) {
    while (std::abs(ok - ng) > 1) {
        int mid = (ok + ng) / 2;
        if (isOK(mid))
            ok = mid;
        else
            ng = mid;
    }
    return ok;
}
template<typename T>
std::map<T, int> compress(std::vector<T>& base_list) {
    std::sort(base_list.begin(), base_list.end());
    base_list.erase(std::unique(base_list.begin(), base_list.end()), base_list.end());
    std::map<T, int> ret;
    rep(i, base_list.size()) {
        ret[base_list[i]] = i;
    }
    return ret;
}
std::vector<int> topologicalSort(const std::vector<std::vector<int>>& graph, bool& flag) {
    std::vector<int> memo(graph.size(), 0);
    for (const auto& vec : graph) {
        for (auto it : vec) {
            memo[it]++;
        }
    }
    std::vector<int> ret(graph.size());

    int cnt = 0, bcnt = 0;
    for (int i = 0; i < graph.size(); i++) {
        if (memo[i] == 0) ret[cnt++] = i;
    }
    if (bcnt + 1 < cnt) flag = true;
    bcnt = cnt;

    for (int i = 0; i < graph.size(); i++) {
        for (auto it : graph[ret[i]]) {
            memo[it]--;
            if (memo[it] == 0) {
                ret[cnt++] = it;
            }
        }
        if (bcnt + 1 < cnt) flag = true;
        bcnt = cnt;
    }

    return ret;
}
std::vector<int> makeDivisors(int n) {
    std::vector<int> re;
    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            re.push_back(i);
            if (i != n / i) re.push_back(n / i);
        }
    }
    return re;
}

class HeavyLightDecomposition {
  public:
    std::vector<std::vector<int>> g;
    int n, t;
    std::vector<int> sz, in, nxt, out, parent, depth;
    void dfs_sz(int v, int par) {
        sz[v] = 1;
        for (auto& u : g[v])
            if (u != par) {
                dfs_sz(u, v);
                sz[v] += sz[u];
                if (g[v][0] == par || sz[u] > sz[g[v][0]]) {
                    std::swap(u, g[v][0]);
                }
            }
    }

    void dfs_hld(int v, int par) {
        in[v] = t++;
        for (auto u : g[v])
            if (u != par) {
                nxt[u] = (u == g[v][0] ? nxt[v] : u);
                parent[u] = (u == g[v][0] ? parent[v] : v);
                depth[u] = (u == g[v][0] ? depth[v] : depth[v] + 1);
                dfs_hld(u, v);
            }
        out[v] = t;
    }

  public:
    HeavyLightDecomposition(const std::vector<std::vector<int>>& g) : g(g), n(g.size()), t(0), sz(n), in(n), nxt(n), out(n), parent(n), depth(n) {
        depth[0] = 0;
        dfs_sz(0, -1);
        dfs_hld(0, -1);
    }
};
template<typename T>
class BIT {
    std::vector<T> dat;
    int siz;

  public:
    BIT() = default;
    BIT(int siz) : siz(siz), dat(siz + 1, 0) {}
    T sum(int i) {
        T s = 0;
        while (i > 0) {
            s += dat[i];
            i -= i & -i;
        }
        return s;
    }
    void add(int i, T x) {
        while (i <= siz) {
            dat[i] += x;
            i += i & -i;
        }
    }
};
struct IoInit {
    IoInit() {
        std::cin.tie(nullptr);
        std::cout.tie(nullptr);
        std::ios::sync_with_stdio(false);
        std::cout << std::fixed << std::setprecision(16);
    }
} io_init;

class Union_Find {

  public:
    vector<int> t, s;
    explicit Union_Find(int max_length) {
        for (int i = 0; i < max_length + 1; ++i) {
            t.push_back(i);
            s.push_back(1);
        }
    }

    void Union(int x, int y) {
        if (same(x, y)) return;
        int tx = Find(x), ty = Find(y);
        if (s[tx] < s[ty]) {
            s[ty] += s[tx];
            t[tx] = ty;
        }
        else if (s[tx] > s[ty]) {
            s[tx] += s[ty];
            t[ty] = tx;
        }
        else if (tx > ty) {
            t[tx] = ty;
            s[ty] += s[tx];
        }
        else {
            t[ty] = tx;
            s[tx] += s[ty];
        }
    }
    int Find(int n) {
        if (t[n] == n)
            return n;
        else
            return Find(t[n]);
    }

    bool same(int x, int y) {
        return Find(x) == Find(y);
    }

    int get_Size(int a) {
        return s[a];
    }
};

signed main() {
    int n, m, k;
    cin >> n >> m >> k;

    vector<int> s(n);
    vector<P> e(m);
    Union_Find tree(n);
    map<P, vector<P>> mp;

    rep(i, m) {
        cin >> e[i];
        e[i].first--;
        e[i].second--;
    }
    rep(i, n) {
        cin >> s[i];
        s[i]--;
    }
    rep(i, m) {
        if (s[e[i].first] == s[e[i].second]) {
            tree.Union(e[i].first, e[i].second);
        }
    }
    rep(i, m) {
        e[i].first = tree.Find(e[i].first);
        e[i].second = tree.Find(e[i].second);
        if (e[i].first > e[i].second) swap(e[i].first, e[i].second);
    }
    sort(e.begin(), e.end());
    e.erase(unique(e.begin(), e.end()), e.end());

    rep(i,m){
        int a=s[e[i].first],b=s[e[i].second];
        if(a!=b){
            if(a>b)swap(a,b);
            mp[{a,b}].push_back(e[i]);
        }
    }

    int q;
    cin>>q;
    map<P,vector<tuple<int,int,int>>> mp2;
    vector<int> ans(q);
    rep(i,q){
        int a,b;
        cin>>a>>b;
        a--;b--;
        int x=s[a],y=s[b];
        if(x>y)swap(x,y);
        mp2[{x,y}].emplace_back(a,b,i);
    }

    for(auto [key,elem]: mp2){
        auto [x,y]=key;
        vector<int> tmp;
        for(auto [u,v]:mp[{x,y}]){
            tmp.push_back(u);tmp.push_back(v);
            tree.Union(u,v);
        }

        for(auto [a,b,i]:elem){
            if(tree.same(a,b))ans[i]=1;
            else ans[i]=0;
        }

        for(auto it:tmp){
            if(tree.t[it]!=it){
                tree.s[tree.t[it]]-=tree.s[it];
                tree.t[it]=it;
            }
        }
    }

    rep(i,q)cout<<ans[i]<<endl;
}