QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#244566 | #4938. Writing Tasks | ckiseki | RE | 3ms | 22244kb | C++14 | 3.7kb | 2023-11-09 11:56:22 | 2023-11-09 11:56:23 |
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];
vector<int> qq;
void dfs(int n, int &siz) {
siz++; qq.pb(n);
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]) {
qq.clear();
int siz = 0;
dfs(i, siz);
if (siz == 8) {
for (auto tt:qq){ cout << tt << endl;
for (auto fu:g[tt]) cout << fu << endl;
cout<<endl;}
assert(false);
}
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;
}
}
for (int i = 1;i < n;i++) {
if (g[i].size() == 0 && !vis[i]) ans++;
}
cout << ans << "\n";
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 22244kb
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: 3ms
memory: 22168kb
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: -100
Runtime Error
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:
1 2 89017 3 2 1 89018 4 89018 89017 2 89020 89017 89018 1 89019 89019 89020 3 89017 89020 89019 4 89018 4 3 89020 2 3 4 89019 1