QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#243752 | #4938. Writing Tasks | ideograph_advantage# | WA | 398ms | 51204kb | C++17 | 3.5kb | 2023-11-08 16:46:13 | 2023-11-08 16:46:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define iter(v) v.begin(), v.end()
#define SZ(v) (int)v.size()
#define pb emplace_back
#define ff first
#define ss second
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U>
void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
while(l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) void()
#define pary(...) void()
#endif
template<class A, class B>
ostream& operator<<(ostream& o, pair<A, B> p){
return o << '(' << p.ff << ',' << p.ss << ')';
}
#define maxn 200005
vector<int> ga[maxn], gc[maxn], gt[maxn], g[maxn];
bool vis[maxn];
void dfs(int n, int &siz) {
siz++;
vis[n] = 1;
for (int v:g[n]) {
if (!vis[v]) {
dfs(v, siz);
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int siza, sizc, sizt;
cin >> siza >> sizc >> sizt;
for (int i = 1;i <= siza;i++) {
//ac
int li; cin >> li;
for (int j = 0;j < li;j++) {
int x;
cin >> x;
ga[i].push_back(x);
}
}
for (int i = 1;i <= siza;i++) {
//at
int li; cin >> li;
for (int j = 0;j < li;j++) {
int x;
cin >> x;
gt[x].push_back(i);
}
}
for (int i = 1;i <= sizc;i++) {
//ct
int li; cin >> li;
for (int j = 0;j < li;j++) {
int x;
cin >> x;
gc[i].push_back(x);
}
}
map<vector<int>, int> mp;
int n = 1;
for (int a = 1;a <= siza;a++) {
for (int c:ga[a]){
int cnt = 0;
for (int t:gc[c]) {
for (int ta:gt[t]) {
if (ta == a) {
vector<int> cy = {a, c, t};
cnt++;
if (!mp[cy]) {
mp[cy] = n++;
}
break;
}
}
}
if (cnt == 2) {
vector<int> vu = {a, c, gc[c][0]}, vv = {a, c, gc[c][1]};
int u = mp[vu], v = mp[vv];
g[u].push_back(v);
g[v].push_back(u);
}
}
}
for (int c = 1;c <= sizc;c++) {
for (int t:gc[c]){
int cnt = 0;
for (int a:gt[t]) {
for (int tc:ga[a]) {
if (tc == c) {
vector<int> cy = {a, c, t};
cnt++;
if (!mp[cy]) {
mp[cy] = n++;
}
break;
}
}
}
if (cnt == 2) {
vector<int> vu = {gt[t][0], c, t}, vv = {gt[t][1], c, t};
int u = mp[vu], v = mp[vv];
g[u].push_back(v);
g[v].push_back(u);
}
}
}
for (int t = 1;t <= sizt;t++) {
for (int a:gt[t]){
int cnt = 0;
for (int c:ga[a]) {
for (int tt:gc[c]) {
if (tt == t) {
vector<int> cy = {a, c, t};
cnt++;
if (!mp[cy]) {
mp[cy] = n++;
}
break;
}
}
}
if (cnt == 2) {
vector<int> vu = {a, ga[a][0], t}, vv = {a, ga[a][1], t};
int u = mp[vu], v = mp[vv];
g[u].push_back(v);
g[v].push_back(u);
}
}
}
/*
for (auto [v, ind]:mp) {
pary(v.begin(), v.end());
debug(ind);
debug();
}
for (int i = 1;i <= n;i++) {
cout << i << ": ";
pary(g[i].begin(), g[i].end());
}
*/
int ans = 0;
for (int i = 1;i <= n;i++) {
if (g[i].size() == 3 && !vis[i]) {
int siz = 0;
dfs(i, siz);
if (siz == 8) ans += 4;
else ans += 3;
}
}
for (int i = 1;i <= n;i++) {
if (g[i].size() == 1 && !vis[i]) {
int siz = 0;
dfs(i, siz);
ans += (siz + 1) / 2;
}
}
for (int i = 1;i <= n;i++) {
if (g[i].size() == 2 && !vis[i]) {
int siz = 0;
dfs(i, siz);
ans += siz / 2;
}
}
cout << ans << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 22240kb
input:
2 3 2 2 1 2 2 2 3 1 1 1 1 1 1 1 1 1 2
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 22204kb
input:
2 2 2 0 1 2 0 2 1 2 2 1 2 0
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 353ms
memory: 48132kb
input:
40623 39265 42226 2 14643 37432 2 29610 20181 2 6441 7614 2 17559 3238 2 39001 17644 2 6431 37097 2 6347 12246 2 1130 1688 2 38583 9078 2 8746 27832 2 13090 39048 2 32647 18777 2 27505 19277 2 31201 25824 2 6133 20344 2 11625 20997 2 18528 35730 0 2 22986 5273 2 10942 38791 2 19025 35679 2 32321 124...
output:
78528
result:
ok single line: '78528'
Test #4:
score: 0
Accepted
time: 342ms
memory: 48256kb
input:
41022 39421 42288 2 26413 2168 2 24182 14199 2 18798 17846 2 3398 19624 2 16796 33998 2 7209 25883 2 26356 13537 2 56 30294 2 34909 20218 2 29727 22116 2 16349 1704 2 9254 18036 2 16197 16096 2 21562 31470 2 14773 10518 2 38025 12573 2 15509 32276 2 9613 12321 2 19146 11395 2 7186 36431 0 2 10098 22...
output:
78840
result:
ok single line: '78840'
Test #5:
score: 0
Accepted
time: 398ms
memory: 51204kb
input:
49395 43808 45888 2 13031 11323 2 41375 4393 2 32137 17908 2 29053 42691 0 2 38335 30970 2 38318 43773 2 22999 22444 0 2 39248 30837 0 2 29807 2360 2 29363 3536 2 8515 41137 2 7890 31441 0 2 31070 6987 2 24295 15517 2 14204 13069 2 32996 40146 2 38164 1478 2 40032 19143 0 2 18430 24119 2 37845 33290...
output:
87616
result:
ok single line: '87616'
Test #6:
score: -100
Wrong Answer
time: 3ms
memory: 22180kb
input:
3 4 3 1 2 2 4 2 2 1 3 1 1 2 2 3 2 3 2 1 3 2 1 3 1 2 1 2
output:
0
result:
wrong answer 1st lines differ - expected: '5', found: '0'