結果
| 問題 | No.2319 Friends+ |
| ユーザー |
 hliuser1
|
| 提出日時 | 2023-12-25 19:56:27 |
| 言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 4,916 bytes |
| コンパイル時間 | 2,358 ms |
| コンパイル使用メモリ | 171,976 KB |
| 実行使用メモリ | 69,948 KB |
| 最終ジャッジ日時 | 2023-12-25 19:56:45 |
| 合計ジャッジ時間 | 17,645 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 18 ms
56,356 KB |
| testcase_01 | AC | 18 ms
56,356 KB |
| testcase_02 | AC | 1,885 ms
63,784 KB |
| testcase_03 | AC | 1,903 ms
63,784 KB |
| testcase_04 | AC | 1,522 ms
63,784 KB |
| testcase_05 | AC | 1,773 ms
63,784 KB |
| testcase_06 | AC | 1,494 ms
63,784 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 | -- | - |
ソースコード
// https://yukicoder.me/problems/no/2319
// really cool problem
//
// Solution 0. use bitsets and bruteforce
//
// Solution 1. sqrt over nodes
// let K = sqrt(M)
// a person is "few" if it has < K friends and "many" if >= K
// there are at most 2M / K ~= K people that are "many"
// to solve a query where x is few, brute force it
// to solve a query where x is many, consider its friends that are:
// a. many - you can check ALL many's for the condition
// b. few - store this as map f[i][j] = # of few friends of the many i in world j
// update naively, it works in O(Q*sqrt M + N*sqrt M + M)
//
// Solution 2. sqrt over queries
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops,strict-overflow")
#pragma GCC target("avx2")
using namespace std;
using HashSet = unordered_set<int>;
using FewCounter = unordered_map<int, vector<int>>;
// signed main2() {
// cout << "sol 1\n";
// freopen("/Users/drymerge/CLionProjects/DEBUG/a.in", "r", stdin);
// freopen("/Users/drymerge/a.out", "w", stdout);
// cin.tie(0)->sync_with_stdio(0);
// int N, M, Q;
// cin >> N >> M;
// int K = sqrt(M);
// vector<int> world(N+1); // world[i] = the world that person i is in
// FewCounter num_few_of; // num_few_of[i].at(w) = # friends of i in world j with < K friends
// vector<int> many; // many = [those with >= K friends]
// vector<HashSet> friends(N+1);
// auto is_many = [&] (int i) {
// return friends[i].size() >= K;
// };
// for (int i = 1; i <= N; ++i)
// cin >> world[i];
// for (int i = 1; i <= M; ++i) {
// int a, b;
// cin >> a >> b;
// friends[a].insert(b);
// friends[b].insert(a);
// }
// for (int i = 1; i <= N; ++i) {
// if (!is_many(i)) continue;
// many.push_back(i);
// num_few_of[i].assign(N+1, 0);
// for (int f : friends[i])
// if (!is_many(f)) {
// int w = world[f];
// ++num_few_of[i].at(w);
// }
// }
// auto solve_many = [&] (int x, int y) {
// int new_world = world[y];
// if (num_few_of[x].at(new_world) > 0)
// goto success;
// for (int m : many)
// if (friends[x].count(m) && world[m] == new_world)
// goto success;
// return "No\n";
// success:
// world[x] = new_world;
// return "Yes\n";
// };
// auto solve_few = [&] (int x, int y) {
// for (int f : friends[x])
// if (world[f] == world[y])
// goto success;
// return "No\n";
// success:
// int old_world = world[x];
// int new_world = world[y];
// for (int f : friends[x]) {
// if (!is_many(f)) continue;
// --num_few_of[f].at(old_world);
// ++num_few_of[f].at(new_world);
// }
// world[x] = new_world;
// return "Yes\n";
// };
// cin >> Q;
// while (Q--) {
// int x, y;
// cin >> x >> y;
// if (world[x] == world[y]) {
// cout << "No\n";
// continue;
// }
// auto ans = is_many(x) ? solve_many(x,y) : solve_few(x,y);
// cout << ans;
// }
// }
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
constexpr size_t MXN = 20001;
constexpr size_t MXM = 400000;
// constexpr size_t MXN = 100;
// constexpr size_t MXM = 100;
signed main() {
// cout << "sol2\n";
// freopen("/Users/drymerge/CLionProjects/DEBUG/a.in", "r", stdin);
// freopen("/Users/drymerge/b.out", "w", stdout);
cin.tie(0)->sync_with_stdio(0);
int N, M, Q;
cin >> N >> M;
short world[MXN];
bitset<MXN> friends[MXN];
short friendships[MXM];
gp_hash_table<short,short> initial_count[MXN];
// initial_count[i][j] = # of friends of i in world j
for (int i = 1; i <= N; ++i)
cin >> world[i];
for (int i = 0; i < M; ++i) {
short a, b;
cin >> a >> b;
friendships[2*i] = a, friendships[2*i+1] = b;
friends[a][b] = true;
friends[b][a] = true;
}
auto reset_map = [&] {
for (int i = 1; i <= N; ++i)
initial_count[i].clear();
for (int i = 0; i < M; ++i) {
short a = friendships[2*i];
short b = friendships[2*i+1];
++initial_count[a][world[b]];
++initial_count[b][world[a]];
}
};
cin >> Q;
int K = sqrt(Q);
int q = 0;
vector<array<short,4>> succeeded;
succeeded.reserve(K);
while (q < Q) {
reset_map();
for (int k = 0; k < K && q < Q; ++k, ++q) {
short x, y;
cin >> x >> y;
if (world[x] == world[y]) {
cout << "No\n";
continue;
}
int start = initial_count[x][world[y]];
for (auto [xl,yl,wx,wy] : succeeded) {
if (wx == world[y] && friends[x][xl])
--start;
if (wy == world[y] && friends[x][xl])
++start;
}
if (start > 0) {
cout << "Yes\n";
succeeded.push_back( {x,y,world[x],world[y]} );
world[x] = world[y];
}
else cout << "No\n";
}
succeeded.resize(0);
}
return 0;
}