oj.uz

Submission #927157

# Submission time Handle Problem Language Result Execution time Memory
927157 2024-02-14T10:42:12 Z vjudge1 Paths (BOI18_paths) C++17
43 / 100
 227 ms 53872 KB 
#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 oo[6][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) {
		memset(oo, 0, sizeof(oo));
		memset(kol, 0, sizeof(kol));
		for(int j : g[i]) {
			kol[a[j]]++;
			for(int mask = 0; mask < (1 << k); ++mask) {
				oo[a[j]][mask] += cnt[j][mask];
			}
		}
		for(int c = 0; c < k; ++c) {
			if(c == a[i]) {
				continue;
			}
			for(int d = 0; d < k; ++d) {
				if(d == a[i] || d == c) {
					continue;
				}	
				int can = (1 << k)-1;
				can ^= (1 << a[i]);
		        can ^= (1 << c);
		        can ^= (1 << d);
		        ans += oo[c][can]*kol[d];
			}
		}
	}
	cout << ans;
    return 0;
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 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 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8536 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 8540 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 13704 KB Output is correct
2 Correct 47 ms 10620 KB Output is correct
3 Correct 174 ms 53072 KB Output is correct
4 Correct 56 ms 15264 KB Output is correct
5 Correct 48 ms 8540 KB Output is correct
6 Correct 121 ms 41068 KB Output is correct
7 Correct 179 ms 53072 KB Output is correct
8 Correct 180 ms 53840 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 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 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8536 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 8540 KB Output is correct
11 Correct 55 ms 13704 KB Output is correct
12 Correct 47 ms 10620 KB Output is correct
13 Correct 174 ms 53072 KB Output is correct
14 Correct 56 ms 15264 KB Output is correct
15 Correct 48 ms 8540 KB Output is correct
16 Correct 121 ms 41068 KB Output is correct
17 Correct 179 ms 53072 KB Output is correct
18 Correct 180 ms 53840 KB Output is correct
19 Correct 52 ms 13652 KB Output is correct
20 Correct 45 ms 10584 KB Output is correct
21 Correct 190 ms 53356 KB Output is correct
22 Correct 61 ms 15232 KB Output is correct
23 Correct 38 ms 8540 KB Output is correct
24 Correct 120 ms 41296 KB Output is correct
25 Correct 186 ms 53392 KB Output is correct
26 Correct 202 ms 53872 KB Output is correct
27 Correct 66 ms 12112 KB Output is correct
28 Correct 74 ms 13680 KB Output is correct
29 Correct 227 ms 53692 KB Output is correct
30 Correct 147 ms 34148 KB Output is correct
31 Incorrect 165 ms 34444 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8696 KB Output is correct
2 Incorrect 37 ms 9776 KB Output isn't correct
3 Halted 0 ms 0 KB -