답안 #926984

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
926984	2024-02-14T06:15:53 Z	vjudge1	Paths (BOI18_paths)	C++17	43 / 100	3000 ms	20948 KB

paths

#include<bits/stdc++.h>

using namespace std;


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

int n, m, k, a[N], cnt[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 main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
	cin >> n >> m >> k;
	for(int i = 1; i <= n; ++i) {
		cin >> 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);
	}
	if(k > 3) {
	    ans=0;
		for(int i = 1; i <= n; ++i) {
			dfs(i);
		}
		cout << ans-n;
		return 0;
	}
	for(int i = 1; i <= n; ++i) {
		int cur = 0;
		memset(cnt, 0, sizeof(cnt));
		for(auto x : g[i]) {
			ans += 2*(cur-cnt[a[x]]);
			cur++;	
			cnt[a[x]]++;
		}
	}
	cout << ans;
    return 0;
}

Subtask #1

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	7260 KB	Output is correct
2	Correct	2 ms	7260 KB	Output is correct
3	Correct	2 ms	7260 KB	Output is correct
4	Correct	2 ms	7260 KB	Output is correct
5	Correct	2 ms	7280 KB	Output is correct
6	Correct	2 ms	7260 KB	Output is correct
7	Correct	2 ms	7260 KB	Output is correct
8	Correct	2 ms	7260 KB	Output is correct
9	Correct	2 ms	7260 KB	Output is correct
10	Correct	2 ms	7256 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	40 ms	10344 KB	Output is correct
2	Correct	35 ms	9308 KB	Output is correct
3	Correct	116 ms	15500 KB	Output is correct
4	Correct	52 ms	10016 KB	Output is correct
5	Correct	36 ms	7516 KB	Output is correct
6	Correct	81 ms	14356 KB	Output is correct
7	Correct	93 ms	20108 KB	Output is correct
8	Correct	104 ms	20948 KB	Output is correct

Subtask #3

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	7260 KB	Output is correct
2	Correct	2 ms	7260 KB	Output is correct
3	Correct	2 ms	7260 KB	Output is correct
4	Correct	2 ms	7260 KB	Output is correct
5	Correct	2 ms	7280 KB	Output is correct
6	Correct	2 ms	7260 KB	Output is correct
7	Correct	2 ms	7260 KB	Output is correct
8	Correct	2 ms	7260 KB	Output is correct
9	Correct	2 ms	7260 KB	Output is correct
10	Correct	2 ms	7256 KB	Output is correct
11	Correct	40 ms	10344 KB	Output is correct
12	Correct	35 ms	9308 KB	Output is correct
13	Correct	116 ms	15500 KB	Output is correct
14	Correct	52 ms	10016 KB	Output is correct
15	Correct	36 ms	7516 KB	Output is correct
16	Correct	81 ms	14356 KB	Output is correct
17	Correct	93 ms	20108 KB	Output is correct
18	Correct	104 ms	20948 KB	Output is correct
19	Correct	42 ms	13140 KB	Output is correct
20	Correct	34 ms	11612 KB	Output is correct
21	Correct	129 ms	20052 KB	Output is correct
22	Correct	53 ms	13396 KB	Output is correct
23	Correct	37 ms	10836 KB	Output is correct
24	Correct	74 ms	18708 KB	Output is correct
25	Correct	122 ms	20052 KB	Output is correct
26	Correct	89 ms	20736 KB	Output is correct
27	Execution timed out	3018 ms	13136 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-

Subtask #4

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	7256 KB	Output is correct
2	Execution timed out	3070 ms	8540 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-