QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #731412 | #9573. Social Media | ucup-team3635# | AC ✓ | 97ms | 22084kb | C++23 | 11.2kb | 2024-11-10 03:29:56 | 2024-11-10 03:29:57 |
Judging History
answer
#ifndef SorahISA
#define SorahISA
#include SorahISA __FILE__ SorahISA
void solve() {
int N, M, K; cin >> N >> M >> K;
vector<int> F(N); cin >> F;
vector<pii> edges(M); cin >> edges;
vector<int> is_friend(K);
for (int &x : F) is_friend[--x] = 1;
int base = 0;
vector<int> C(K);
map<pii, int> cnt;
for (auto &[u, v] : edges) {
--u, --v;
if (is_friend[u] and is_friend[v]) ++base;
else if (is_friend[u]) ++C[v];
else if (is_friend[v]) ++C[u];
else if (u == v) ++C[u];
else ++cnt[minmax(u, v)];
}
// debug(C);
// debug(cnt);
int ans = base;
for (auto [e, val] : cnt) chmax(ans, base + C[e.first] + C[e.second] + val);
sort(RALL(C));
chmax(ans, base + C[0] + (K >= 2 ? C[1] : 0));
print(ans);
}
int32_t main() {
fastIO();
int t = 1; cin >> t;
for (int _ = 1; _ <= t; ++_) {
// cout << "Case #" << _ << ": ";
solve();
}
return 0;
}
#else
#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// #include <bits/extc++.h>
// #include <tr2/dynamic_bitset>
using i64 = long long;
using i128 = __int128;
#define int i64
using f80 = long double;
using f128 = __float128;
#define double f80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;
// #define X first
// #define Y second
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())
// template <size_t D, typename T> struct Vec : vector<Vec<D-1, T>> {
// static_assert(D >= 1, "Vector dimension must be greater than zero!");
// template <typename... Args> Vec(int n = 0, Args... args) : vector<Vec<D-1, T>>(n, Vec<D-1, T>(args...)) {}
// };
// template <typename T> struct Vec<1, T> : vector<T> {
// Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {}
// };
template <typename T, typename U> istream& operator >> (istream &is, pair<T, U> &p)
{ return is >> p.first >> p.second; }
template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &p)
{ return os << p.first << " " << p.second; }
template <typename T> istream& operator >> (istream &is, vector<T> &vec)
{ for (size_t i = 0; i < size(vec); ++i) is >> vec[i]; return is; }
template <typename T> ostream& operator << (ostream &os, const vector<T> &vec)
{ for (size_t i = 0; i < size(vec); ++i) { if (i) os << " "; os << vec[i]; } return os; }
#ifdef local
#define fastIO() void()
#define debug(...) \
_color.emplace_back("\u001b[31m"), \
fprintf(stderr, "%sAt [%s], line %d: (%s) = ", _color.back().c_str(), __FUNCTION__, __LINE__, #__VA_ARGS__), \
_do(__VA_ARGS__), _color.pop_back(), \
fprintf(stderr, "%s", _color.back().c_str())
#define print(...) \
fprintf(stdout, "%s", "\u001b[36m"), \
_P(__VA_ARGS__), \
fprintf(stdout, "%s", "\u001b[0m")
deque<string> _color{"\u001b[0m"};
template <typename T> concept is_string = is_same_v<T, string&> or is_same_v<T, const string&>;
template <typename T> concept is_iterable = requires (T _t) { begin(_t); };
template <typename T> inline void _print_err(T &&_t);
template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>);
template <size_t I, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &);
template <size_t I, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(const tuple<U...> &_t);
template <size_t I, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &);
template <size_t I, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(tuple<U...> &_t);
inline void _do() { cerr << "\n"; }
template <typename T> inline void _do(T &&_t) { _print_err(_t), cerr << "\n"; }
template <typename T, typename ...U> inline void _do(T &&_t, U &&..._u) { _print_err(_t), cerr << ", ", _do(_u...); }
#else
#define fastIO() cin.tie(0)->sync_with_stdio(0)
#define debug(...) void()
#define print(...) _P(__VA_ARGS__)
#endif
inline void _P() { cout << "\n"; }
template <typename T> inline void _P(T &&_t) { cout << _t << "\n"; }
template <typename T, typename ...U> inline void _P(T &&_t, U &&..._u) { cout << _t << " ", _P(_u...); }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int getRand(int L, int R) {
if (L > R) swap(L, R);
return (int)(rng() % ((uint64_t)R - L + 1) + L);
}
template <typename T, typename U> bool chmin(T &lhs, U rhs) { return lhs > rhs ? lhs = rhs, 1 : 0; }
template <typename T, typename U> bool chmax(T &lhs, U rhs) { return lhs < rhs ? lhs = rhs, 1 : 0; }
/// below are Fast I/O and _print_err templates ///
/*
/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///
#include <unistd.h>
const int S = 65536;
int OP = 0;
char OB[S];
inline char RC() {
static char buf[S], *p = buf, *q = buf;
return p == q and (q = (p = buf) + read(0, buf, S)) == buf ? -1 : *p++;
}
inline int RI() {
static char c;
int a;
while (((c = RC()) < '0' or c > '9') and c != '-' and c != -1);
if (c == '-') {
a = 0;
while ((c = RC()) >= '0' and c <= '9') a *= 10, a -= c ^ '0';
}
else {
a = c ^ '0';
while ((c = RC()) >= '0' and c <= '9') a *= 10, a += c ^ '0';
}
return a;
}
inline void WI(int n, char c = '\n') {
static char buf[20], p;
if (n == 0) OB[OP++] = '0';
p = 0;
if (n < 0) {
OB[OP++] = '-';
while (n) buf[p++] = '0' - (n % 10), n /= 10;
}
else {
while (n) buf[p++] = '0' + (n % 10), n /= 10;
}
for (--p; p >= 0; --p) OB[OP++] = buf[p];
OB[OP++] = c;
if (OP > S-20) write(1, OB, OP), OP = 0;
}
/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///
*/
#ifdef local
template <typename T> inline void _print_err(T &&_t) { cerr << _t; }
template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>) {
_color.emplace_back(_color.back()), ++_color.back()[3];
cerr << _color.back() << "[";
for (bool _first = true; auto &_x : _t) {
if (!_first) cerr << ", ";
_print_err(_x), _first = false;
}
cerr << "]" << (_color.pop_back(), _color.back());
}
template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &) {
cerr << ")" << (_color.pop_back(), _color.back());
}
template <size_t I = 0, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(const tuple<U...> &_t) {
if (!I) {
_color.emplace_back(_color.back()), ++_color.back()[3];
cerr << _color.back();
}
cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}
template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &) {
cerr << ")" << (_color.pop_back(), _color.back());
}
template <size_t I = 0, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(tuple<U...> &_t) {
if (!I) {
_color.emplace_back(_color.back()), ++_color.back()[3];
cerr << _color.back();
}
cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}
#endif
#endif
/**
*
*
*
* iiiiii iiiiiiiiii iiiiiiiiiiiiii
* iiiiiiiiiiiii iiiiiii iiii iiiiiiiiiiiiiii ii iiii
* iiiiiiii iiiiiiiii iiii iiii iii iii iiiiiiiiii
* iiiiiii iiiiii iiii iiii ii iiiiiiiiii iiii iiii
* iiiiii iiiii iiii iiii iii iiii iiiiiiiiiiiiiiiii ii
* iiiiii iiiiiii iiiiiii iiiiiiii iii iiiiiiiiiiiiii iii iiii
* iiiiii iiiiiii iiiii ii iiii iiiiiiiiiii iiii iii iiii iiii iii
* iiiii iiiiiiii ii iiiii iiii iiiiiiiii iii iii iii iii ii iiii
* iiiiii iiiiiiii iiiii iiiii iiiiiiiiiiiiiiii iii iii ii iii iii iiii
* iiiii iiiiii iiii iiiiii iiiiiii iii iii iiii ii i ii iii iii
* iiiiii iiii iiiiiiiiiiiiiii iii iiii iiiii iii ii iii iii ii
* iiiii iiiiiiii iiiiiiiiii iiii iiiiiiiii ii iii ii
* iiiii iiiiii iiii iiiii iii ii ii i
* iiiiii iiiiiiii iiiii iiiii ii ii ii
* iiiii iiii iiii iiiiiiiiiiii ii
* iii iiii iiii iiiiiiii
* iiiii iiii
* iiii iiii
* iiii iiiii
* iii iiiii
* iii iiiii
* iii iiiiii
* iiiiiiiii
* iiiiii
*
*
*
**/
这程序好像有点Bug，我给组数据试试？
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
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: 17ms
memory: 3652kb
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: 17ms
memory: 3832kb
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: 23ms
memory: 4056kb
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: 93ms
memory: 21928kb
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: 90ms
memory: 20716kb
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: 46ms
memory: 13528kb
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: 97ms
memory: 22056kb
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: 54ms
memory: 22084kb
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