結果
| 問題 | No.2319 Friends+ |
| ユーザー |
 GEX777
|
| 提出日時 | 2023-05-27 12:41:41 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 13,723 bytes |
| コンパイル時間 | 1,691 ms |
| コンパイル使用メモリ | 150,260 KB |
| 実行使用メモリ | 114,300 KB |
| 最終ジャッジ日時 | 2024-06-07 15:50:16 |
| 合計ジャッジ時間 | 19,737 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,820 KB |
| testcase_01 | AC | 1 ms
5,376 KB |
| testcase_02 | AC | 2,386 ms
107,264 KB |
| testcase_03 | AC | 2,336 ms
107,264 KB |
| testcase_04 | AC | 2,185 ms
107,264 KB |
| testcase_05 | AC | 2,257 ms
107,244 KB |
| testcase_06 | AC | 2,390 ms
107,264 KB |
| testcase_07 | TLE | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
ソースコード
/**
* @file main.cpp
* @brief 俺の競技プログラミングのデッキ
* @author Gex777
* @date update:2023/04/21
* @details boost
*/
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <string>
#include <sstream>
#include <climits>
#include <bitset>
#include <deque>
#include <cassert>
#include <list>
#include <queue>
#include <valarray>
#include <complex>
#include <bitset>
// #include <atcoder/all> //ACL(環境依存)
// #include <boost/multiprecision/cpp_int.hpp>
using namespace std;
// using namespace atcoder;
// namespace mp = boost::multiprecision;
// using Bint = mp::cpp_int;
// 独自型定義
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
using AdjacencyList = map<int, vi>;
using EdgeAdjacencyList = map<int, vector<int, int>>;
// マクロの宣言
#define all(x) x.begin(), x.end()
// 定数宣言
constexpr double PI = 3.141592653589793;
constexpr ll MOD998 = 998244353;
constexpr ll MOD107 = 1'000'000'007;
/****************************************************
*************ここから下は自作ライブラリ**************
****************************************************/
// コンテナの中身を表示, 1行で出力をする, debug用
template <typename T>
void printv(T &a)
{
for (const auto &x : a)
{
cout << x << " ";
}
puts("");
return;
}
// コンテナの中身を表示, 二次元配列用
template <typename T>
void printvv(T &a)
{
for (const auto &x : a)
{
printv(x);
}
}
// コンテナの中身を表示, pair型
template <typename T>
void print_vpair(const T &a)
{
for (const auto &x : a)
{
cout << "(" << x.first << ", " << x.second << "), ";
}
puts("");
return;
}
template <class T>
inline bool chmin(T &a, T b)
{
if (a > b)
{
a = b;
return true;
}
return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
if (a < b)
{
a = b;
return true;
}
return false;
}
// コンテナの中身を表示, 改行して出力をする, debug用
template <typename T>
void println(T &a)
{
for (const auto &x : a)
{
cout << x << endl;
}
return;
}
// 1~Nまでの総和を求める
ll sum_from_1_to_N(ll N)
{
if (N < 1LL)
{
return 0;
}
if ((N & 1) == 0) // even
{
return N / 2 * (N + 1);
}
else // odd
{
return (N + 1) / 2 * N;
}
}
// A~Nまでの総和を求める
ll sum_from_A_to_B(ll A, ll B)
{
return sum_from_1_to_N(B) - sum_from_1_to_N(A);
}
// a^bを求める, 繰り返し2乗法を用いる,3番目の引数はModを取る場合に設定
ll intPowMod(ll a, ll b, const ll MOD = LLONG_MAX)
{
ll ans = 1;
ll A = a;
while (b > 0)
{
int n = b % 2;
b /= 2;
if (n == 1)
{
ans *= A % MOD;
ans %= MOD;
}
A = ((A % MOD) * (A % MOD)) % MOD;
}
return ans;
}
ld arg_to_rad(ld arg)
{
return (arg * PI / 180.0);
}
ld rad_to_arg(ld rad)
{
return rad * 180.0 / PI;
}
// C(n, m)を求める
ll combination(const ll n, const ll m)
{
assert(n >= m); // n>=mは保証される
ll up = 1;
ll down = 1;
for (int i = n; i > n - m; i--)
{
up *= i;
}
for (int i = m; i >= 2; i--)
{
down *= i;
}
return up / down;
}
// 動的計画法で前処理,O(N**2)
vvll combination_table(const int MAX_N = 50)
{
vvll com = vvll(MAX_N + 1, vll(MAX_N + 1, 0)); // 前計算の結果を保存
com[0][0] = 1;
for (int i = 1; i <= MAX_N; ++i)
{
com[i][0] = 1;
for (int j = 1; j <= MAX_N; j++)
{
com[i][j] = (com[i - 1][j - 1] + com[i - 1][j]);
}
}
return com;
}
// a÷bをMODで割ったあまりを返す関数
ll DivisionMod(ll a, ll b, ll MOD)
{
return (a * intPowMod(b, MOD - 2, MOD)) % MOD;
}
// C(n, r)をModで割った余りを返す関数, 3番めの引数を入れないと通常のConbination
ll combinationMod(ll n, ll r, ll MOD = LLONG_MAX)
{
// 分子upを求める
ll up = 1;
for (ll i = n - r + 1; i <= n; ++i)
{
up = (up * i) % MOD;
}
// 分母downを求める
ll down = 1;
for (ll i = 1; i <= r; ++i)
down = (down * i) % MOD;
return DivisionMod(up, down, MOD);
}
// a,bの最大公約数を求める, A>=B>=0の時, 計算量O(logB)
long long GCD(long long a, long long b)
{
if (b == 0)
return a;
else
return GCD(b, a % b);
}
// 拡張ユークリッドの互助法, 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす (x, y) が格納される
long long extGCD(long long a, long long b, long long &x, long long &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
long long d = extGCD(b, a % b, y, x);
y -= a / b * x;
return d;
}
// 最小公倍数
ll LCM(ll a, ll b)
{
return a * b / GCD(a, b);
}
// 素数判定, P->true, not_P->false
bool check_Prime(ll N)
{
if (N == 2)
return true;
if (N == 1 || (N & 1) == 0)
return false;
for (ll i = 3; i <= sqrt(N); i += 2)
{
if (N % i == 0)
return false;
}
return true;
}
// 素因数分解,key:素数, value:指数のmap<ll,ll>を返す
map<ll, ll> prime_factorize(ll number)
{
map<ll, ll> table;
for (ll i = 2; i * i <= number; ++i)
{
while (number % i == 0)
{
table[i]++;
number /= i;
}
}
if (number != 1LL)
{
table[number]++;
}
return table;
}
/* エラストステネス and 高速素因数分解
prime->IsPrime[i]=i; not prime ->最小の素因数 */
vi Eratosthenes(size_t max_number)
{
vi IsPrime(max_number + 1);
// tableの初期化
for (int i = 1; i < IsPrime.size(); ++i)
{
IsPrime[i] = i;
}
for (int i = 2; i <= sqrt(max_number); ++i)
{
for (int j = i; j <= max_number; j += i)
{
if (IsPrime[j] == j)
{
IsPrime[j] = i;
}
}
}
return IsPrime;
}
// O(N)でNの階乗を求める
ll factorial(const ll N)
{
ll ans = 1;
for (ll i = 1; i <= N; ++i)
{
ans *= i;
}
return ans;
}
// Run Length Encoding, ランレングス圧縮
template <typename T>
vector<pair<T, int>> RLE(const vector<T> &A)
{
vector<pair<T, int>> rle;
rle.push_back({A.front(), 1});
for (int i = 1; i < A.size(); ++i)
{
if (rle.back().first == A[i])
{
rle.back().second++;
}
else
{
rle.push_back({A[i], 1});
}
}
return rle;
}
vector<pair<char, int>> RLE(const string &S)
{
vector<pair<char, int>> rle;
rle.push_back({S.front(), 1});
for (int i = 1; i < S.size(); ++i)
{
if (rle.back().first == S[i])
{
rle.back().second++;
}
else
{
rle.push_back({S[i], 1});
}
}
return rle;
}
void DEBUG_INDICATE()
{
static int cnt = 0;
cout << "-----DEBUG:" << cnt++ << "------" << endl;
return;
}
/* RMQ：[0,n-1] について、区間ごとの最小値を管理する構造体
update(i,x): i 番目の要素を x に更新。O(log(n))
query(a,b): [a,b) での最小の要素を取得。O(log(n))
*/
template <typename T>
struct RangeMinimumQuery
{
const T INF = numeric_limits<T>::max();
int n; // 葉の数
vector<T> dat; // 完全二分木の配列
RangeMinimumQuery(int n_) : n(), dat(n_ * 4, INF)
{ // 葉の数は 2^x の形
int x = 1;
while (n_ > x)
{
x *= 2;
}
n = x;
}
void update(int i, T x)
{
i += n - 1;
dat[i] = x;
while (i > 0)
{
i = (i - 1) / 2; // parent
dat[i] = min(dat[i * 2 + 1], dat[i * 2 + 2]);
}
}
// the minimum element of [a,b)
T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
T query_sub(int a, int b, int k, int l, int r)
{
if (r <= a || b <= l)
{
return INF;
}
else if (a <= l && r <= b)
{
return dat[k];
}
else
{
T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
return min(vl, vr);
}
}
};
/* RMQ：[0,n-1] について、区間ごとの最小値を管理する構造体
update(i,x): i 番目の要素を x に更新。O(log(n))
query(a,b): [a,b) での最小の要素を取得。O(log(n))
*/
template <typename T>
struct RangeMaximumQuery
{
const T INF = numeric_limits<T>::min();
int n; // 葉の数
vector<T> dat; // 完全二分木の配列
RangeMaximumQuery(int n_) : n(), dat(n_ * 4, INF)
{ // 葉の数は 2^x の形
int x = 1;
while (n_ > x)
{
x *= 2;
}
n = x;
}
void update(int i, T x)
{
i += n - 1;
dat[i] = x;
while (i > 0)
{
i = (i - 1) / 2; // parent
dat[i] = max(dat[i * 2 + 1], dat[i * 2 + 2]);
}
}
// the minimum element of [a,b)
T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
T query_sub(int a, int b, int k, int l, int r)
{
if (r <= a || b <= l)
{
return INF;
}
else if (a <= l && r <= b)
{
return dat[k];
}
else
{
T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
return max(vl, vr);
}
}
};
// Union-Find
struct UnionFind
{
vector<int> par, rank, siz;
// 構造体の初期化
UnionFind(int n) : par(n, -1), rank(n, 0), siz(n, 1) {}
// 根を求める
int root(int x)
{
if (par[x] == -1)
return x; // x が根の場合は x を返す
else
return par[x] = root(par[x]); // 経路圧縮
}
// x と y が同じグループに属するか (= 根が一致するか)
bool issame(int x, int y)
{
return root(x) == root(y);
}
// x を含むグループと y を含むグループを併合する
bool unite(int x, int y)
{
int rx = root(x), ry = root(y); // x 側と y 側の根を取得する
if (rx == ry)
return false; // すでに同じグループのときは何もしない
// union by rank
if (rank[rx] < rank[ry])
swap(rx, ry); // ry 側の rank が小さくなるようにする
par[ry] = rx; // ry を rx の子とする
if (rank[rx] == rank[ry])
rank[rx]++; // rx 側の rank を調整する
siz[rx] += siz[ry]; // rx 側の siz を調整する
return true;
}
// x を含む根付き木のサイズを求める
int size(int x)
{
return siz[root(x)];
}
};
/* BIT: 区間和の更新や計算を行う構造体
初期値は a_1 = a_2 = ... = a_n = 0
計算量は全て O(logn)
*/
template <typename T>
struct BIT
{
int n; // 配列の要素数(数列の要素数+1)
vector<T> bit; // データの格納先
// 構造体の初期化
BIT(int n_) : n(n_ + 1), bit(n, 0) {}
// add(i,x): a_i += x とする
void add(int i, T x)
{
for (int idx = i; idx < n; idx += (idx & -idx))
{
bit[idx] += x;
}
}
// sum(i): a_1 + a_2 + ... + a_i を計算する
T sum(int i)
{
T s(0);
for (int idx = i; idx > 0; idx -= (idx & -idx))
{
s += bit[idx];
}
return s;
}
};
/*********************************************
*************ライブラリ終わり******************
***********************************************/
int main()
{
int N, M;
cin >> N >> M;
constexpr int BNUM = 20000;
vector<bitset<BNUM>> Friend(N);
vector<bitset<BNUM>> world(N);
// DEBUG_INDICATE();
// cout << Friend.back().size() << endl;
for (int i = 0; i < N; ++i)
{
int p;
cin >> p;
p--;
world[i].set(p);
}
// DEBUG_INDICATE();
for (int i = 0; i < M; ++i)
{
int A, B;
cin >> A >> B;
--A;
--B;
// cout <<"A="<< A <<" B="<< B << endl;
Friend[A].set(B);
Friend[B].set(A);
}
int Q;
cin >> Q;
vs ans(Q, "No");
// DEBUG_INDICATE();
for (int i = 0; i < Q; ++i)
{
// cout << "Q=" << i << endl;
int X, Y;
cin >> X >> Y;
--X;
--Y;
if (world[X] == world[Y])
{
// puts("same world");
continue;
}
for (int j = 0; j < N; ++j)
{
if (X != j && Friend[X][j] && world[j] == world[Y]) // Xとjはフレンド
{
world[X] = world[Y];
ans[i] = "Yes";
break;
}
}
}
println(ans);
}