QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#726932 | #9573. Social Media | ucup-team3646# | AC ✓ | 91ms | 23012kb | C++20 | 6.1kb | 2024-11-09 10:30:11 | 2024-11-09 10:30:14 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define rep2(i, l, r) for(ll i = l; i < r; i++)
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
/* ---- */
#define all(A) A.begin(), A.end()
#define elif else if
using pii = pair<ll, ll>;
bool chmin(auto &a, const auto &b) {return a > b ? a = b, 1 : 0;}
bool chmax(auto &a, const auto &b) {return a < b ? a = b, 1 : 0;}
struct IOSetup {
IOSetup() {
cin.tie(0);
ios::sync_with_stdio(0);
}
} iosetup;
template<class T>
void print(vector<T> a) {
for (auto x : a) cerr << x << ' ';
cerr << endl;
}
void print(auto x) {
cerr << x << endl;
}
template<class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
cerr << head << ' ';
print(forward<Tail>(tail)...);
}
#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>
#ifdef _MSC_VER
#include <intrin.h>
#endif
#if __cplusplus >= 202002L
#include <bit>
#endif
namespace atcoder {
namespace internal {
#if __cplusplus >= 202002L
using std::bit_ceil;
#else
unsigned int bit_ceil(unsigned int n) {
unsigned int x = 1;
while (x < (unsigned int)(n)) x *= 2;
return x;
}
#endif
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
constexpr int countr_zero_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
} // namespace internal
} // namespace atcoder
namespace atcoder {
#if __cplusplus >= 201703L
template <class S, auto op, auto e> struct segtree {
static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
"op must work as S(S, S)");
static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
"e must work as S()");
#else
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
#endif
public:
segtree() : segtree(0) {}
explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {
size = (int)internal::bit_ceil((unsigned int)(_n));
log = internal::countr_zero((unsigned int)size);
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) const {
assert(0 <= p && p < _n);
return d[p + size];
}
S prod(int l, int r) const {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() const { return d[1]; }
template <bool (*f)(S)> int max_right(int l) const {
return max_right(l, [](S x) { return f(x); });
}
template <class F> int max_right(int l, F f) const {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*f)(S)> int min_left(int r) const {
return min_left(r, [](S x) { return f(x); });
}
template <class F> int min_left(int r, F f) const {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
} // namespace atcoder
using namespace atcoder;
ll op(ll a, ll b) {return max(a, b);}
ll e() {return 0LL;}
void solve() {
ll N, M, K; cin >> N >> M >> K;
vector<ll> F(N);
vector<ll> isf(K, 0);
for (auto &f : F) {
cin >> f;
f--;
isf[f] = 1;
}
ll base = 0;
vector<ll> one(K, 0);
vector<vector<ll>> two(K);
rep(i, M) {
ll a, b; cin >> a >> b;
a--, b--;
ll s = isf[a] + isf[b];
if (s == 2) base += 1;
else if (s == 1) {
if (isf[a] > isf[b]) swap(a, b);
// isf[a] == 0
one[a] += 1;
}
else {
if (a == b) {
one[a] += 1;
}
else {
two[a].emplace_back(b);
two[b].emplace_back(a);
}
}
}
segtree<ll, op, e> seg(one);
ll res = base;
rep(k, K) {
ll tmp = one[k];
seg.set(k, 0LL);
for (auto f : two[k]) {
seg.set(f, seg.get(f) + 1);
}
tmp += seg.all_prod();
chmax(res, base + tmp);
for (auto f : two[k]) {
seg.set(f, seg.get(f) - 1);
}
seg.set(k, one[k]);
}
cout << res << '\n';
return;
}
int main() {
ll T; cin >> T;
while (T--) {
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3536kb
input:
5 4 12 7 5 7 3 6 3 6 2 2 1 4 2 4 1 3 7 6 4 1 5 4 1 1 1 1 2 1 3 7 2 7 6 2 4 1 2 3 2 2 5 5 4 2 6 4 6 2 6 1 1 2 1 1 2 2 1 2 1 2 1 2 2 1 100 24 11 11 24
output:
9 5 1 1 1
result:
ok 5 number(s): "9 5 1 1 1"
Test #2:
score: 0
Accepted
time: 14ms
memory: 3632kb
input:
10000 19 12 20 8 12 1 5 11 7 17 13 19 6 3 9 10 15 14 20 4 18 16 4 11 7 1 8 4 16 19 1 13 15 2 16 2 8 7 3 15 11 13 5 20 18 14 17 14 20 2 9 1 12 8 11 10 17 18 16 3 15 5 14 20 13 7 15 10 3 2 5 16 7 8 6 1 6 4 18 16 1 8 4 1 20 6 6 9 4 15 7 5 14 9 1 3 18 9 15 18 17 15 11 14 7 19 7 3 1 2 5 6 4 7 5 1 4 5 3 1...
output:
12 14 1 19 6 5 1 11 19 4 3 10 4 1 4 19 15 2 18 4 17 5 1 2 5 17 3 2 6 15 6 3 6 4 4 7 3 7 4 1 16 15 2 3 6 12 12 7 6 8 8 6 8 11 16 1 4 9 8 14 2 6 19 19 16 8 20 14 8 12 7 9 6 8 2 17 9 5 5 3 6 6 20 8 13 11 10 5 3 6 3 1 8 5 8 11 7 14 10 9 9 11 7 9 5 2 8 14 10 5 3 5 5 10 1 6 9 16 5 3 19 1 4 8 8 10 4 2 1 15...
result:
ok 10000 numbers
Test #3:
score: 0
Accepted
time: 20ms
memory: 3732kb
input:
1000 59 96 80 10 66 50 63 15 2 28 41 21 58 45 42 14 79 32 33 37 52 1 74 57 27 72 77 8 49 40 78 31 12 70 62 73 26 69 24 3 65 67 23 6 47 17 38 54 80 5 64 13 51 44 71 39 34 75 19 55 30 68 61 14 14 26 7 28 53 3 51 79 68 24 50 1 39 45 74 18 13 12 5 68 41 1 32 30 69 13 61 59 26 68 17 56 74 14 22 25 71 41 ...
output:
60 83 4 5 2 90 23 125 72 7 49 81 25 9 40 22 78 51 7 47 77 19 49 73 134 114 104 121 180 3 2 4 92 86 146 9 20 2 74 3 78 32 19 63 5 79 17 16 54 131 83 23 45 153 33 137 67 98 8 21 6 53 12 89 14 97 9 142 25 100 108 87 56 15 43 153 2 165 41 132 116 160 118 167 63 6 16 8 3 67 4 91 4 34 8 83 32 34 119 63 17...
result:
ok 1000 numbers
Test #4:
score: 0
Accepted
time: 19ms
memory: 3832kb
input:
100 37 237 517 339 497 190 114 508 454 321 58 102 392 289 207 291 459 16 320 55 378 269 63 407 244 397 101 357 328 412 62 70 468 457 21 253 453 509 169 400 202 476 217 222 418 58 440 109 90 110 266 197 159 398 412 317 259 239 500 34 178 508 329 162 192 409 467 144 223 300 2 289 96 366 191 427 142 12...
output:
6 4 11 6 6 7 11 11 2 3 14 2 4 2 3 2 2 5 7 3 3 5 3 13 8 7 17 6 2 8 3 9 3 10 2 3 3 2 2 2 5 12 2 5 5 959 369 56 1045 15 67 394 757 82 1008 56 2 1317 1590 217 37 345 32 515 103 326 1628 1450 293 12 397 358 403 420 220 150 392 588 3 978 1296 97 49 1377 7 1764 627 1652 188 65 11 12 2 2 1 5 1 2 2 2
result:
ok 100 numbers
Test #5:
score: 0
Accepted
time: 83ms
memory: 21888kb
input:
1 100 200000 200000 9411 13081 102149 19907 193611 24114 159730 105867 96529 35050 21890 102981 87777 182418 96659 118374 76106 107614 179526 45826 56158 33510 42240 53971 75573 98727 113513 35449 165290 167552 180720 151348 194140 132021 197828 138348 52399 151728 27676 75498 122825 15163 89905 262...
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 91ms
memory: 21552kb
input:
1 10000 200000 200000 125539 129221 106895 82089 118673 102890 99009 89855 30685 139232 82330 30021 87868 184659 66982 166291 148020 179364 42952 142770 119906 181288 92853 152547 189430 17447 7734 93014 55411 67422 67242 28915 103728 75454 199937 132948 87129 181803 14914 8713 163118 33277 88390 16...
output:
527
result:
ok 1 number(s): "527"
Test #7:
score: 0
Accepted
time: 55ms
memory: 17996kb
input:
1 100000 200000 200000 176259 110770 87448 103054 67926 181667 95184 41139 164840 76118 118577 22469 96470 178388 28793 14208 195743 59626 40970 7011 7847 104874 362 194226 168695 127655 101955 109363 169723 134588 10660 147697 13315 51590 34750 103356 121858 179173 2151 198823 146514 51392 54171 15...
output:
50020
result:
ok 1 number(s): "50020"
Test #8:
score: 0
Accepted
time: 70ms
memory: 22612kb
input:
1 1 200000 200000 200000 2 1 3 2 4 1 5 4 6 3 7 4 8 2 9 7 10 3 11 7 12 1 13 8 14 1 15 4 16 5 17 13 18 6 19 11 20 19 21 8 22 6 23 20 24 8 25 17 26 2 27 26 28 6 29 28 30 4 31 7 32 24 33 16 34 5 35 32 36 11 37 29 38 7 39 6 40 27 41 6 42 18 43 20 44 22 45 3 46 26 47 9 48 16 49 1 50 1 51 34 52 33 53 45 54...
output:
1
result:
ok 1 number(s): "1"
Test #9:
score: 0
Accepted
time: 50ms
memory: 23012kb
input:
1 1 200000 200000 200000 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 5...
output:
1
result:
ok 1 number(s): "1"
Extra Test:
score: 0
Extra Test Passed