oj.uz

Submission #80773

# Submission time Handle Problem Language Result Execution time Memory
80773 2018-10-22T10:10:17 Z farukkastamonuda Paths (BOI18_paths) C++14
0 / 100
 399 ms 26476 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define lo long long 
#define inf 1000000000
#define md 1000000007
#define li 300005
#define mp make_pair
#define pb push_back
using namespace std;
int n, m, k, A[li], col[li][6], cev, x, y;
lo int anacev;
vector< int > v[li];
pair< int , int > p[li];
int main(){
	scanf("%d %d %d", &n, &m, &k);
	for(int i = 1;i <= n;i++) scanf("%d", &A[i]);
	if(k == 0){
		printf("0\n");
		return 0;
	}
	for(int i = 1; i <= m; i++){
		scanf("%d %d", &x, &y);
		p[i] = mp(x,y);
		if(A[x] != A[y]) cev++;
		v[x].pb(y);
		v[y].pb(x);
		col[x][A[y]]++;
		col[y][A[x]]++;
	}
	anacev += 1ll * cev * 2;
	if(k == 2){
		printf("%lld\n", anacev);
		return 0;
	}
	for(int i = 1; i <= n; i++){
		if((int)v[i].size() >= 2){
			for(int j = 1;j <= k; j++){
				if(A[i] == j) continue;
				for(int t = j+1; t <= k; t++){
					if(A[i] == t || t == j) continue;
					anacev += 1ll * col[i][j] * col[i][t] * 2; 
				}
			}
		}
	}
	if(k == 3){
		printf("%lld\n", anacev);
		return 0;
	}
	for(int i = 1; i <= m; i++){
		int node1 = p[i].fi;
		int node2 = p[i].se;
		if(A[node1] == A[node2]) continue;
		for(int j = 1; j <= k; j++){
			if(j == A[node1] || j == A[node2]) continue;
			for(int t = 1; t <= k; t++){
				if(j == t || t == A[node1] || t == A[node2]) continue;
				anacev += 1ll * col[node1][j] * col[node2][t] * 2;
			}
		}
	}
	if(k == 4){
		printf("%lld\n", anacev);
		return 0;
	}
	
	return 0;
}

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
paths.cpp:17:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1;i <= n;i++) scanf("%d", &A[i]);
                            ~~~~~^~~~~~~~~~~~~
paths.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7484 KB Output is correct
3 Correct 8 ms 7484 KB Output is correct
4 Correct 9 ms 7644 KB Output is correct
5 Incorrect 9 ms 7644 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 13568 KB Output is correct
2 Correct 107 ms 13568 KB Output is correct
3 Correct 399 ms 26476 KB Output is correct
4 Correct 145 ms 26476 KB Output is correct
5 Incorrect 136 ms 26476 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7484 KB Output is correct
3 Correct 8 ms 7484 KB Output is correct
4 Correct 9 ms 7644 KB Output is correct
5 Incorrect 9 ms 7644 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 26476 KB Output isn't correct
2 Halted 0 ms 0 KB -