oj.uz

Submission #80788

# Submission time Handle Problem Language Result Execution time Memory
80788 2018-10-22T10:37:12 Z farukkastamonuda Paths (BOI18_paths) C++14
0 / 100
 396 ms 43960 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;
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

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.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 19876 KB Output is correct
2 Correct 102 ms 19876 KB Output is correct
3 Correct 396 ms 43960 KB Output is correct
4 Correct 209 ms 43960 KB Output is correct
5 Incorrect 205 ms 43960 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 7496 KB Output is correct
3 Correct 9 ms 7496 KB Output is correct
4 Correct 8 ms 7640 KB Output is correct
5 Incorrect 8 ms 7640 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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