結果
問題 | No.2319 Friends+ |
ユーザー |
|
提出日時 | 2023-05-27 14:11:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 777 ms / 3,000 ms |
コード長 | 3,124 bytes |
コンパイル時間 | 1,451 ms |
コンパイル使用メモリ | 129,980 KB |
最終ジャッジ日時 | 2025-02-13 09:15:39 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 45 |
ソースコード
/*** @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;}// コンテナの中身を表示, 改行して出力をする, debug用template <typename T>void println(T &a){for (const auto &x : a){cout << x << endl;}return;}/*##############################################################################################*/int main(){int N, M;cin >> N >> M;constexpr int BNUM = 20000;vector<bitset<BNUM>> Friend(N); // i番目の人とj番目の人はフレンドかvector<bitset<BNUM>> world(N); // world[i]にj番目の人がいるかvector<int> pos(N); // i番目の人が今いるワールドの番号for (int i = 0; i < N; ++i){int p;cin >> p;p--;world[p].set(i);pos[i] = p;}for (int i = 0; i < M; ++i){int A, B;cin >> A >> B;--A;--B;Friend[A].set(B);Friend[B].set(A);}int Q;cin >> Q;vs ans(Q, "No");for (int i = 0; i < Q; ++i){int X, Y;cin >> X >> Y;--X;--Y;if ((pos[X] != pos[Y]) && (Friend[X]&world[pos[Y]]).any()) // XのフレンドがとYのいるワールドもいる{world[pos[X]].reset(X);world[pos[Y]].set(X);pos[X] = pos[Y];ans[i] = "Yes";}// cout << "pos=";// printv(pos);}println(ans); // クエリの結果を出力}