結果

問題 No.1983 [Cherry 4th Tune C] 南の島のマーメイド
コンテスト
ユーザー 7deQSJCy8c4Hg7I
提出日時 2022-11-24 22:56:07
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 6,614 bytes
コンパイル時間 4,717 ms
コンパイル使用メモリ 252,920 KB
実行使用メモリ 22,232 KB
最終ジャッジ日時 2024-10-01 11:08:22
合計ジャッジ時間 19,373 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 38 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using Graph = vector<vector<int>>;
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<long long>;
using vb = vector<bool>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
using pii = pair<long long, long long>;
using mint = modint1000000007;
const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); i++)
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)
#define rrep(i, n) for (ll i = (1); i < (ll)(n + 1); i++)
#define repd(i, n) for (ll i = n - 1; i >= 0; i--)
#define rrepd(i, n) for (ll i = n; i >= 1; i--)
#define ALL(n) begin(n), end(n)
#define fore(i, a) for (auto &i : a)
#define IN(a, x, b) (a <= x && x < b)
#define INIT                        \
  std::ios::sync_with_stdio(false); \
  std::cin.tie(0);

template <class T>
inline T CHMAX(T &a, const T b) {
  return a = (a < b) ? b : a;
}
template <class T>
inline T CHMIN(T &a, const T b) {
  return a = (a > b) ? b : a;
}

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
ll GCD(ll m, ll n) {
  // ベースケース
  if (n == 0) return m;

  // 再帰呼び出し
  return GCD(n, m % n);
}

ll minlong = 0;
void DFS(int &n, int &i, vvll A, vll &AQ, ll &k, int &ati, vll &H,
         vll &KAISUU) {
  AQ.push_back(i);
  KAISUU[i]--;

  for (int j = 0; j < n; j++)
    if (A[i][j] == true && KAISUU[j] != 0) {
      DFS(n, j, A, AQ, k, ati, H, KAISUU);
    }

  if (AQ.size() >= minlong && AQ.size() % k == 0) {
    H[ati]++;
  }
  minlong = AQ.size();
  KAISUU[AQ[AQ.size() - 1]]++;
  AQ.pop_back();
}
long long Power(long long a, long long b, long long m) {
  long long p = a, Answer = 1;
  for (int i = 0; i < 63; i++) {
    ll wari = (1LL << i);
    if ((b / wari) % 2 == 1) {
      Answer = (Answer * p) % m;  // 「a の 2^i 乗」が掛けられるとき
    }
    p = (p * p) % m;
  }
  return Answer;
}

// a ÷ b を m で割った余りを返す関数
long long Division(long long a, long long b, long long m) {
  return (a * Power(b, m - 2, m)) % m;
}

// nCr mod 1000000007 を返す関数
long long nCk(ll n, ll r) {
  const long long M = 1000000007;

  // 手順 1: 分子 a を求める
  long long a = 1;
  for (int i = 1; i <= n; i++) a = (a * i) % M;

  // 手順 2: 分母 b を求める
  long long b = 1;
  for (int i = 1; i <= r; i++) b = (b * i) % M;
  for (int i = 1; i <= n - r; i++) b = (b * i) % M;

  // 手順 3: 答えを求める
  return Division(a, b, M);
}
using Interval = pair<ll, ll>;
class SegmentTree {
 public:
  long long dat[300000], siz = 1;

  // 要素 dat の初期化を行う（最初は全部ゼロ）
  void init(int N) {
    siz = 1;
    while (siz < N) siz *= 2;
    for (int i = 1; i < siz * 2; i++) dat[i] = 0;
  }

  // クエリ 1 に対する処理
  void update(int pos, int x) {
    pos = pos + siz;
    dat[pos] = x;
    while (pos >= 2) {
      pos /= 2;
      dat[pos] = dat[pos * 2] + dat[pos * 2 + 1];
    }
  }

  // クエリ 2 に対する処理
  // u は現在のセル番号、[a, b) はセルに対応する半開区間、[l, r)
  // は求めたい半開区間
  long long query(int l, int r, int a, int b, long long u) {
    if (r <= a || b <= l) return 0;       // 一切含まれない場合
    if (l <= a && b <= r) return dat[u];  // 完全に含まれる場合
    int m = (a + b) / 2;
    int AnswerL = query(l, r, a, m, u * 2);
    int AnswerR = query(l, r, m, b, u * 2 + 1);
    return AnswerL + AnswerR;
  }
};
// 終点時間でsortをかけるのに必要(区間スケジューリング問題など)
bool cmp(const Interval &a, const Interval &b) { return a.second < b.second; }
void DFS(vvll A, vb &B, ll a) {
  B[a] = true;
  rep(i, A[a].size()) {
    if (!B[A[a][i]]) {
      // B[A[a][i]] = true;
      DFS(A, B, A[a][i]);
    }
  }
  return;
}
vll dycstra(vector<vector<pair<ll, ll>>> G, ll N) {
  vb kaku(N, false);
  vll cur(N, INF);
  cur[0] = 0;
  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> Q;
  Q.push(make_pair(cur[0], 0));
  while (!Q.empty()) {
    ll pos = Q.top().second;
    Q.pop();
    if (kaku[pos]) continue;
    kaku[pos] = true;
    for (ll i = 0; i < G[pos].size(); i++) {
      ll nex = G[pos][i].first;
      ll cost = G[pos][i].second;
      if (cur[nex] > cur[pos] + cost) {
        cur[nex] = cur[pos] + cost;
        Q.push(make_pair(cur[nex], nex));
      }
    }
  }
  return cur;
}
long long kan(ll N, map<ll, ll> MP) {
  if (MP[N] != 0) {
    return MP[N];
  }

  else {
    return MP[N] = kan(N / 2, MP) + kan(N / 3, MP);
  }
}
double PQRS(ll N, ll K, ll M, ll count, vector<vector<vector<double>>> &G) {
  double a, b, c;
  // cout << N << ' ' << K << ' ' << M << endl;
  if (N == 99) a = (double)N * (double)count / (double)(N + K + M);
  if (N != 99) {
    if (G[N + 1][K][M] == -1) {
      G[N + 1][K][M] = PQRS(N + 1, K, M, count + 1, G);
    }
    a = G[N + 1][K][M] * (double)N / (double)(N + K + M);
  }
  if (M == 99) b = (double)M * (double)count / (double)(N + K + M);
  if (M != 99) {
    if (G[N][K][M + 1] == -1) {
      G[N][K][M + 1] = PQRS(N, K, M + 1, count + 1, G);
    }
    b = G[N][K][M + 1] * (double)M / (double)(N + K + M);
  }
  if (K == 99) c = (double)count * (double)K / (double)(N + K + M);
  if (K != 99) {
    if (G[N][K + 1][M] == -1) {
      G[N][K + 1][M] = PQRS(N, K + 1, M, count + 1, G);
    }
    c = G[N][K + 1][M] * (double)K / (double)(N + K + M);
  }
  // cout << N << endl;
  return a + b + c;
}
int main() {
  ll N,M,Q;
  cin >> N >> M >>Q;
  vll u(M), v(M);
  vvll G(N);
  rep(i, M) {
    cin >> u[i] >> v[i];
    G[u[i] - 1].push_back(v[i] - 1);
    G[v[i] - 1].push_back(u[i] - 1);
  }
  vll cur(N);
  rep(i, N) { cur[i] = G[i].size(); }
  queue<ll> QU;
  rep(i, N) {
    if (cur[i] == 1) {
      QU.push(i);
    }
  }
  while (QU.size()) {
    ll a = QU.front();
    QU.pop();
    cur[a]--;
    for (auto V : G[a]) {
      if (cur[V]) {
        cur[V]--;
        if (cur[V] == 1) QU.push(V);
      }
    }
  }
  dsu d(N);
  rep(i, M) {
    if (cur[v[i] - 1]>=2 && cur[u[i] - 1]>=2) continue;
    d.merge(v[i] - 1, u[i] - 1);
  }
  rep(i, Q) {
    ll a, b;
    cin >> a >> b;
    if (d.leader(a - 1) == d.leader(b - 1))
      cout << "Yes" << endl;
    else
      cout << "No" << endl;
  }
}
0