結果
問題 | No.2319 Friends+ |
ユーザー |
|
提出日時 | 2023-05-28 19:40:00 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,639 ms / 3,000 ms |
コード長 | 1,012 bytes |
コンパイル時間 | 6,816 ms |
コンパイル使用メモリ | 267,716 KB |
最終ジャッジ日時 | 2025-02-13 15:47:50 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 45 |
ソースコード
#include <bits/stdc++.h>using namespace std;int main () {int N, M;cin >> N >> M;std::vector<int> A(N);for (auto& a : A) cin >> a;vector<vector<int>> gr(N);for (int i = 0; i < M; i ++) {int a, b;cin >> a >> b;gr[--a].push_back(--b);gr[b].push_back(a);}int s = max(1, (int)sqrt(M));vector<vector<int>> bb(N);vector<unordered_map<int, int>> X(N);for (int i = 0; i < N; i ++) {if (gr[i].size() > s) {for (auto v : gr[i]) {bb[v].push_back(i);}} else {for (auto v : gr[i]) {X[v][A[i]] ++;}}}int Q;cin >> Q;while (Q--) {int x, y;cin >> x >> y;x --; y --;if (A[x] == A[y]) {puts("No");continue;}int a = A[y];bool ok = false;if (X[x][a] > 0) {ok = true;} else {for (auto v : bb[x]) {ok = ok || (a == A[v]);}}if (ok) {puts("Yes");if (gr[x].size() <= s) {for (auto v : gr[x]) {X[v][A[x]] --;X[v][a] ++;}}A[x] = a;} else {puts("No");}}}