oj.uz

답안 #927006

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
927006 2024-02-14T06:34:04 Z vjudge1 Paths (BOI18_paths) C++17
23 / 100
 3000 ms 53072 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 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -