답안 #864344

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
864344	2023-10-22T14:42:04 Z	maks007	Paths (BOI18_paths)	C++14	70 / 100	398 ms	41816 KB

paths

#include "bits/stdc++.h"

using namespace std;

#define int long long

vector <int> color;
vector <vector <int>> cntColor, g;

signed main () {
	int n, m, k;
	cin >> n >> m >> k;
	color.resize(n);
	cntColor.resize(n, vector <int> (k + 1, 0));
	g.resize(n);
	for(int i = 0; i < n; i ++) cin >> color[i];
	for(int i = 0, u, v; i < m; i ++) {
		cin >> u >> v;
		u --, v --;
		g[u].push_back(v);
		g[v].push_back(u);
		cntColor[u][color[v]] ++;
		cntColor[v][color[u]] ++;
	}
	
	int ans = 0;
	for(int color2 = 1; color2 <= k; color2 ++) {
		for(int i = 0; i < n; i ++) {
			if(color[i] == color2) {
				for(int color1 = 1; color1 <= k; color1 ++) {
					if(color1 == color2) continue;
					ans += cntColor[i][color1];
					if(k == 2) continue;
					for(int color3 = color1 + 1; color3 <= k; color3 ++) {
						if(color3 == color2) continue;
						ans += 2 * (cntColor[i][color1] * cntColor[i][color3]);
					}
				}
			}
		}
  	}
  //	cout << ans << " ";
  	if(k >= 4) {
  		for(int v = 0; v < n; v ++) {
  			for(auto u : g[v]) {
  				if(color[u] == color[v]) continue;
  				for(int i = 1; i <= k; i ++) {
  					if(i == color[u] || color[v] == i) continue;
  					for(int j = 1; j <= k; j ++) {
  						if(j == i || j == color[u] || j == color[v]) continue;
  						ans += cntColor[v][i] * cntColor[u][j];
  					}
  				}
  				
  			}
  		}
  	}
  	if(k >= 5) {
  		for(int v = 0; v < n; v ++) {
  			for(auto u : g[v]) {
  				for(auto  i : g[v]) {
  				
  				}
  			}
  		}
  	}
  	cout << ans;
	return 0;
}

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:61:17: warning: unused variable 'i' [-Wunused-variable]
   61 |       for(auto  i : g[v]) {
      |                 ^
paths.cpp:60:15: warning: unused variable 'u' [-Wunused-variable]
   60 |      for(auto u : g[v]) {
      |               ^

Subtask #1

23.0 / 23.0

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

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	133 ms	8020 KB	Output is correct
2	Correct	85 ms	7520 KB	Output is correct
3	Correct	332 ms	41716 KB	Output is correct
4	Correct	137 ms	11092 KB	Output is correct
5	Correct	140 ms	11032 KB	Output is correct
6	Correct	244 ms	29640 KB	Output is correct
7	Correct	324 ms	41448 KB	Output is correct
8	Correct	330 ms	41796 KB	Output is correct

Subtask #3

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	572 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	133 ms	8020 KB	Output is correct
12	Correct	85 ms	7520 KB	Output is correct
13	Correct	332 ms	41716 KB	Output is correct
14	Correct	137 ms	11092 KB	Output is correct
15	Correct	140 ms	11032 KB	Output is correct
16	Correct	244 ms	29640 KB	Output is correct
17	Correct	324 ms	41448 KB	Output is correct
18	Correct	330 ms	41796 KB	Output is correct
19	Correct	135 ms	7924 KB	Output is correct
20	Correct	91 ms	7400 KB	Output is correct
21	Correct	318 ms	41428 KB	Output is correct
22	Correct	148 ms	11348 KB	Output is correct
23	Correct	138 ms	11104 KB	Output is correct
24	Correct	254 ms	29632 KB	Output is correct
25	Correct	326 ms	41324 KB	Output is correct
26	Correct	334 ms	41816 KB	Output is correct
27	Correct	96 ms	7572 KB	Output is correct
28	Correct	137 ms	9808 KB	Output is correct
29	Correct	396 ms	41300 KB	Output is correct
30	Correct	290 ms	24516 KB	Output is correct
31	Correct	271 ms	24516 KB	Output is correct
32	Correct	398 ms	41440 KB	Output is correct
33	Correct	1 ms	348 KB	Output is correct
34	Correct	0 ms	344 KB	Output is correct
35	Correct	0 ms	348 KB	Output is correct
36	Correct	0 ms	348 KB	Output is correct
37	Correct	0 ms	348 KB	Output is correct
38	Correct	0 ms	348 KB	Output is correct
39	Correct	0 ms	348 KB	Output is correct
40	Correct	0 ms	348 KB	Output is correct
41	Correct	0 ms	348 KB	Output is correct
42	Correct	0 ms	348 KB	Output is correct

Subtask #4

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Incorrect	34 ms	2608 KB	Output isn't correct
3	Halted	0 ms	0 KB	-