QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#244566#4938. Writing TasksckisekiRE 3ms22244kbC++143.7kb2023-11-09 11:56:222023-11-09 11:56:23

Judging History

你现在查看的是最新测评结果

  • [2023-11-09 11:56:23]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:22244kb
  • [2023-11-09 11:56:22]
  • 提交

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";
}

Details

Tip: Click on the bar to expand more detailed information

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


result: