QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#243752#4938. Writing Tasksideograph_advantage#WA 398ms51204kbC++173.5kb2023-11-08 16:46:132023-11-08 16:46:13

Judging History

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

  • [2023-11-08 16:46:13]
  • 评测
  • 测评结果:WA
  • 用时:398ms
  • 内存:51204kb
  • [2023-11-08 16:46:13]
  • 提交

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'