結果
問題 | No.2319 Friends+ |
ユーザー |
![]() |
提出日時 | 2023-07-25 01:13:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 533 ms / 3,000 ms |
コード長 | 1,852 bytes |
コンパイル時間 | 2,150 ms |
コンパイル使用メモリ | 199,608 KB |
最終ジャッジ日時 | 2025-02-15 18:48:33 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 45 |
ソースコード
#include <bits/stdc++.h>using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int N,M;cin >> N >> M;vector<int>P(N);for(int i = 0; i < N; i++) {cin >> P[i];P[i]--;}vector<vector<int>>road1(N);vector<vector<int>>road2(N);for(int i = 0; i < M; i++) {int A,B;cin >> A >> B;A--;B--;road1[A].push_back(B);road1[B].push_back(A);}int B = 334;vector<vector<int>>cnt(N);for(int i = 0; i < N; i++) {if(road1[i].size() >= B) {cnt[i].resize(N);}}for(int i = 0; i < N; i++) {for(int j:road1[i]) {if(road1[j].size() >= B) {road2[i].push_back(j);cnt[j][P[i]]++;}}}int Q;cin >> Q;while(Q--) {int X,Y;cin >> X >> Y;X--;Y--;if(P[X] == P[Y]) {cout << "No" << "\n";continue;}if(road1[X].size() >= B) {if(cnt[X][P[Y]]) {cout << "Yes" << "\n";for(int i:road2[X]) {cnt[i][P[X]]--;cnt[i][P[Y]]++;}P[X] = P[Y];}else {cout << "No" << "\n";}}else {bool f = false;for(int i:road1[X]) {if(P[i] == P[Y]) f = true;}if(f) {cout << "Yes" << "\n";for(int i:road2[X]) {cnt[i][P[X]]--;cnt[i][P[Y]]++;}P[X] = P[Y];}else {cout << "No" << "\n";}}}}