Submission #927006

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
927006	2024-02-14T06:34:04 Z	vjudge1	Paths (BOI18_paths)	C++17	23 / 100	3000 ms	53072 KB

paths

#include<bits/stdc++.h>

using namespace std;


const int N = (int)3e5+3;
const int MOD = (int)1e6+3;
const int B1 = 450;
const int B2 = 450;

int n, m, k, a[N], kol[6];
vector<int> g[N];
bool used[6];
long long ans;

void dfs(int v) {
	used[a[v]] = 1;
	ans++;
	for(auto to : g[v]) {
		if(!used[a[to]]) {
			dfs(to);
		}
	}
	used[a[v]] = 0;
}

int cnt[N][32];

int main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
	cin >> n >> m >> k;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		a[i]--;
	}
	for(int i = 1; i <= m; ++i) {
		int u, v;
		cin >> u >> v;
		if(a[u] == a[v]) {
			continue;
		}
		ans += 2;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i = 1; i <= n; ++i) {
		int cur = 0;
		memset(kol, 0, sizeof(kol));
		for(auto x : g[i]) {
			ans += 2*(cur-kol[a[x]]);
			cur++;	
			kol[a[x]]++;
		}
	}
	for(int i = 1; i <= n; ++i) {
		for(int mask = 0; mask < (1 << k); ++mask) {
			for(int j : g[i]) {
				if(!(mask >> a[j] & 1)) {
					continue;
				}		
				cnt[i][mask]++;
			}
		}
	}
	for(int i = 1; i <= n; ++i) {
		int can = (1 << k)-1;
		can ^= (1 << a[i]);
		for(int j : g[i]) {
			can ^= (1 << a[j]);
			for(int k : g[i]) {
				if(!(can >> a[k] & 1)) {
					continue;
				}
				can ^= (1 << a[k]);
				ans += cnt[j][can];
				can ^= (1 << a[k]);
			}
			can ^= (1 << a[j]);
		}
	}
	cout << ans;
    return 0;
}

Subtask #1

23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	8540 KB	Output is correct
2	Correct	2 ms	8540 KB	Output is correct
3	Correct	2 ms	8540 KB	Output is correct
4	Correct	2 ms	8536 KB	Output is correct
5	Correct	2 ms	8540 KB	Output is correct
6	Correct	3 ms	8564 KB	Output is correct
7	Correct	2 ms	8540 KB	Output is correct
8	Correct	2 ms	8540 KB	Output is correct
9	Correct	2 ms	8540 KB	Output is correct
10	Correct	2 ms	8536 KB	Output is correct

Subtask #2

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	101 ms	13524 KB	Output is correct
2	Correct	281 ms	10744 KB	Output is correct
3	Correct	168 ms	53072 KB	Output is correct
4	Correct	56 ms	15348 KB	Output is correct
5	Correct	51 ms	8536 KB	Output is correct
6	Execution timed out	3032 ms	41104 KB	Time limit exceeded
7	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	8540 KB	Output is correct
2	Correct	2 ms	8540 KB	Output is correct
3	Correct	2 ms	8540 KB	Output is correct
4	Correct	2 ms	8536 KB	Output is correct
5	Correct	2 ms	8540 KB	Output is correct
6	Correct	3 ms	8564 KB	Output is correct
7	Correct	2 ms	8540 KB	Output is correct
8	Correct	2 ms	8540 KB	Output is correct
9	Correct	2 ms	8540 KB	Output is correct
10	Correct	2 ms	8536 KB	Output is correct
11	Correct	101 ms	13524 KB	Output is correct
12	Correct	281 ms	10744 KB	Output is correct
13	Correct	168 ms	53072 KB	Output is correct
14	Correct	56 ms	15348 KB	Output is correct
15	Correct	51 ms	8536 KB	Output is correct
16	Execution timed out	3032 ms	41104 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-

Subtask #4

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	8536 KB	Output is correct
2	Incorrect	95 ms	9800 KB	Output isn't correct
3	Halted	0 ms	0 KB	-