oj.uz

Submission #80780

# Submission time Handle Problem Language Result Execution time Memory
80780 2018-10-22T10:23:42 Z farukkastamonuda Paths (BOI18_paths) C++14
0 / 100
 413 ms 44072 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]]++;
	}
	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 7548 KB Output is correct
3 Correct 9 ms 7548 KB Output is correct
4 Correct 8 ms 7548 KB Output is correct
5 Incorrect 8 ms 7576 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 19752 KB Output is correct
2 Correct 92 ms 19752 KB Output is correct
3 Correct 413 ms 44072 KB Output is correct
4 Correct 180 ms 44072 KB Output is correct
5 Incorrect 184 ms 44072 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 7548 KB Output is correct
3 Correct 9 ms 7548 KB Output is correct
4 Correct 8 ms 7548 KB Output is correct
5 Incorrect 8 ms 7576 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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