Submission #80788

#	Time	Username	Problem	Language	Result	Execution time	Memory
80788		farukkastamonuda	Paths (BOI18_paths)	C++14	0 / 100	396 ms	43960 KiB

paths

#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;
lo int n, m, k, A[li], col[li][8], cev, x, y;
lo int anacev;
vector< lo int > v[li];
pair< lo int , lo int > p[li];
int main(){
	scanf("%lld %lld %lld", &n, &m, &k);
	for(int i = 1; i <= n; i++) scanf("%lld", &A[i]);
	if(k == 0){
		printf("0\n");
		return 0;
	}
	for(int i = 1; i <= m; i++){
		scanf("%lld %lld", &x, &y);
		p[i] = mp(x,y);
		if(x==y) continue;
		if(A[x] != A[y]) cev++;
		v[x].pb(y);
		v[y].pb(x);
		col[x][A[y]]++;
		col[y][A[x]]++;
	}
	for(int i = 1;i <= n;i++){
		for(int j = 1; j <= k; j++){
			if(j == A[i]) continue;
			anacev += col[i][j];
		}
	}
	//anacev += 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 += 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 += col[node1][j] * col[node2][t] * 2;
			}
		}
	}
	if(k == 4){
		printf("%lld\n", anacev);
		return 0;
	}
	
	return 0;
}

Compilation message (stderr)

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("%lld %lld %lld", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
paths.cpp:17:35: 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("%lld", &A[i]);
                              ~~~~~^~~~~~~~~~~~~~~
paths.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 23
• Subtask 2: 0 / 20
• Subtask 3: 0 / 27
• Subtask 4: 0 / 30