oj.uz

Submission #63173

# Submission time Handle Problem Language Result Execution time Memory
63173 2018-08-01T03:55:35 Z 윤교준(#1834) Paths (BOI18_paths) C++11
20 / 100
 514 ms 31788 KB 
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define befv(V) ((V)[(sz(V)-2)])
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
void fg(vector<int> G[], int a, int b) { G[a].eb(b); G[b].eb(a); }

namespace kis2 {
	int *A, *B, *C;

	int N, M;
	int Ans;

	int run(int _N, int _M, int _A[], int _B[], int _C[]) {
		N = _N; M = _M; A = _A; B = _B; C = _C;

		for(int i = 1; i <= M; i++)
			if(C[A[i]] != C[B[i]])
				Ans++;
		return Ans<<1;
	}
}

namespace kis3 {
	static const int MAXN = 300005;

	vector<int> G[MAXN];

	int *A, *B, *C;

	int N, M;
	ll Ans;

	ll run(int _N, int _M, int _A[], int _B[], int _C[]) {
		N = _N; M = _M; A = _A; B = _B; C = _C;

		for(int i = 1; i <= M; i++)
			fg(G, A[i], B[i]);

		Ans = kis2::run(N, M, A, B, C);

		for(int i = 1; i <= N; i++) {
			int cnt[5] = {0, };
			for(int v : G[i]) {
				cnt[C[v]]++;
			}
			for(int a = 1; a <= 4; a++) for(int b = a+1; b <= 4; b++) {
				if(a == C[i] || b == C[i]) continue;
				Ans += ll(cnt[a]) * cnt[b] * 2;
			}
		}

		return Ans;
	}
}


int A[300005], B[300005];
int C[300005];
int N, M, K;

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> M >> K;
	for(int i = 1; i <= N; i++) cin >> C[i];
	for(int i = 1; i <= M; i++) cin >> A[i] >> B[i];

	if(1 == K) puts("0");
	else if(2 == K) printf("%d\n", kis2::run(N, M, A, B, C));
	else if(3 == K) printf("%lld\n", kis3::run(N, M, A, B, C));

	return 0;
}

Subtask #1
0 / 23.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 16364 KB Output is correct
2 Correct 109 ms 18384 KB Output is correct
3 Correct 450 ms 28956 KB Output is correct
4 Correct 152 ms 28956 KB Output is correct
5 Correct 106 ms 28956 KB Output is correct
6 Correct 320 ms 29428 KB Output is correct
7 Correct 437 ms 31076 KB Output is correct
8 Correct 514 ms 31788 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 30.0

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