結果
| 問題 | No.2319 Friends+ |
| ユーザー |
 hliuser1
|
| 提出日時 | 2023-12-26 06:09:43 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,804 bytes |
| コンパイル時間 | 5,573 ms |
| コンパイル使用メモリ | 309,628 KB |
| 実行使用メモリ | 72,268 KB |
| 最終ジャッジ日時 | 2023-12-26 06:10:22 |
| 合計ジャッジ時間 | 36,439 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 20 ms
64,220 KB |
| testcase_01 | AC | 21 ms
57,416 KB |
| testcase_02 | AC | 1,293 ms
69,452 KB |
| testcase_03 | AC | 1,267 ms
69,708 KB |
| testcase_04 | AC | 1,228 ms
69,580 KB |
| testcase_05 | AC | 1,352 ms
69,452 KB |
| testcase_06 | AC | 1,248 ms
69,324 KB |
| testcase_07 | AC | 1,035 ms
71,940 KB |
| testcase_08 | AC | 1,036 ms
72,140 KB |
| testcase_09 | AC | 1,032 ms
71,980 KB |
| testcase_10 | AC | 1,035 ms
71,896 KB |
| testcase_11 | AC | 1,037 ms
72,140 KB |
| testcase_12 | AC | 22 ms
57,420 KB |
| testcase_13 | AC | 22 ms
57,420 KB |
| testcase_14 | AC | 22 ms
57,420 KB |
| testcase_15 | AC | 22 ms
57,420 KB |
| testcase_16 | AC | 22 ms
57,420 KB |
| testcase_17 | AC | 21 ms
57,416 KB |
| testcase_18 | AC | 309 ms
59,212 KB |
| testcase_19 | AC | 1,158 ms
71,964 KB |
| testcase_20 | AC | 553 ms
68,940 KB |
| testcase_21 | AC | 507 ms
65,868 KB |
| testcase_22 | AC | 574 ms
70,092 KB |
| testcase_23 | AC | 882 ms
71,580 KB |
| testcase_24 | AC | 770 ms
71,344 KB |
| testcase_25 | AC | 686 ms
72,012 KB |
| testcase_26 | AC | 671 ms
71,680 KB |
| testcase_27 | AC | 649 ms
71,116 KB |
| testcase_28 | AC | 686 ms
71,244 KB |
| testcase_29 | AC | 606 ms
70,860 KB |
| testcase_30 | AC | 558 ms
69,964 KB |
| testcase_31 | AC | 564 ms
68,428 KB |
| testcase_32 | AC | 462 ms
65,228 KB |
| testcase_33 | AC | 413 ms
64,332 KB |
| testcase_34 | AC | 360 ms
61,132 KB |
| testcase_35 | AC | 277 ms
59,212 KB |
| testcase_36 | AC | 523 ms
72,268 KB |
| testcase_37 | TLE | - |
| 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 (cheating)
//
// 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. ft. Jerry -> sqrt over queries
// for each chunk, recompute a map of for each person i, how many friends they have in world j
// then for each query, loop over the previous queries in the chunk and simulate. if by the end,
// you still have at least one friend in world[y], ur good
// the map computations take M sqrt(Q) time total, the rest is Q sqrt(Q)
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
using HashSet = unordered_set<int>;
using FewCounter = unordered_map<int, vector<int>>;
// signed main2() {
// 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;
// }
// }
// SOLUTION 2: TLEs sadly. could not get it to pass
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
struct chash {
const int RANDOM = (long long)(make_unique<char>().get()) ^ chrono::high_resolution_clock::now().time_since_epoch().count();
static unsigned long long hash_f(unsigned long long x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
static unsigned hash_combine(unsigned a, unsigned b) { return a * 31 + b; }
int operator()(int x) const { return hash_f(x)^RANDOM; }
};
template <typename K, typename V>
using HashTable = gp_hash_table<K,V,chash>;
// template <typename K, typename V>
// using HashTable = unordered_map<K,V>;
constexpr size_t MXN = 20001;
constexpr size_t MXM = 400000;
// constexpr size_t MXN = 100;
// constexpr size_t MXM = 100;
constexpr size_t SQR = 450;
#define all(x) begin(x), end(x)
signed main() {
cin.tie(0)->sync_with_stdio(0);
int N, M, Q;
cin >> N >> M;
short world[MXN];
bitset<MXN> friends[MXN];
vector<short> friendss[MXN];
short friendships[MXM];
HashTable<int, short> initial_count[MXN];
// short initial_count[MXN][SQR];
short X[SQR], Y[SQR];
vector<int> whos_involved;
// gp_hash_table<int,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;
friendss[a].push_back(b);
friendss[b].push_back(a);
friendships[2*i] = a, friendships[2*i+1] = b;
friends[a][b] = true;
friends[b][a] = true;
}
auto reset_map = [&] {
sort( all(whos_involved) );
whos_involved.resize(unique(all(whos_involved)) - begin(whos_involved));
for (int c : whos_involved) {
if (!initial_count[c].empty())
initial_count[c].clear();
for (int f : friendss[c]) {
++initial_count[c][world[f]];
}
}
// 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;
HashTable<int,vector<int>> succeeded_wx, succeeded_wy;
while (q < Q) {
int last = min(Q, q + K);
for (int k = q; k < last; ++k) {
cin >> X[k-q] >> Y[k-q];
whos_involved.push_back(X[k-q]);
whos_involved.push_back(Y[k-q]);
}
reset_map();
for (int k = 0; k < K && q < Q; ++k, ++q) {
short x = X[k], y = Y[k];
if (world[x] == world[y]) {
cout << "No\n";
continue;
}
int start = initial_count[x][world[y]];
for (int xl : succeeded_wx[ world[y] ]) {
start -= (friends[x][xl]);
}
for (int xl : succeeded_wy[ world[y] ]) {
start += (friends[x][xl]);
}
if (start > 0) {
cout << "Yes\n";
succeeded_wx[world[x]].push_back(x);
succeeded_wy[world[y]].push_back(x);
world[x] = world[y];
}
else cout << "No\n";
}
succeeded_wx.clear();
succeeded_wy.clear();
whos_involved.clear();
}
return 0;
}