답안 #63182 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
63182	2018-08-01T04:15:17 Z	윤교준(#1834)	Paths (BOI18_paths)	C++11	100 / 100	699 ms	44716 KB

paths

#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[6] = {0, };
			for(int v : G[i]) {
				cnt[C[v]]++;
			}
			for(int a = 1; a <= 5; a++) for(int b = a+1; b <= 5; b++) {
				if(a == C[i] || b == C[i]) continue;
				Ans += ll(cnt[a]) * cnt[b] * 2;
			}
		}

		return Ans;
	}
}

namespace kis4 {
	static const int MAXN = 300005;

	vector<int> G[MAXN];
	int D[MAXN][6];

	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;
		Ans = kis3::run(N, M, A, B, C);

		for(int i = 1; i <= M; i++) fg(G, A[i], B[i]);
		for(int i = 1; i <= N; i++) for(int v : G[i]) D[i][C[v]]++;

		for(int i = 1, a, b; i <= M; i++) {
			a = A[i]; b = B[i];
			if(C[a] == C[b]) continue;
			D[a][C[b]]--; D[b][C[a]]--;

			for(int ca = 1; ca <= 5; ca++) for(int cb = ca+1; cb <= 5; cb++) {
				if(ca == C[a] || cb == C[a] || ca == C[b] || cb == C[b]) continue;
				Ans += ll(D[a][ca]) * D[b][cb] * 2;
				Ans += ll(D[b][ca]) * D[a][cb] * 2;
			}

			D[a][C[b]]++; D[b][C[a]]++;
		}

		return Ans;
	}
}

namespace kis5 {
	static const int MAXN = 100005;

	vector<pii> KV[5];
	vector<int> TKV;

	vector<int> G[MAXN];
	int D[MAXN][6];

	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;
		Ans = kis4::run(N, M, A, B, C);

		for(int i = 1; i <= M; i++) fg(G, A[i], B[i]);
		for(int i = 1; i <= N; i++) for(int v : G[i]) D[i][C[v]]++;

		for(int key = 0; key < (1<<5); key++) {
			int cnt = 0;
			for(int i = 0; i < 5; i++) if(key & (1<<i)) cnt++;
			if(2 == cnt) TKV.eb(key);
		}
		for(int i = 0; i < 5; i++) {
			for(int a : TKV) for(int b : TKV) {
				if((a & (1<<i)) || (b & (1<<i)) || (a & b) || a > b) continue;
				KV[i].eb(a, b);
			}
		}

		for(int i = 1; i <= N; i++) {
			ll cnt[1<<5] = {0, };

			for(int v : G[i]) if(C[i] != C[v]) {
				for(int c = 0; c < 5; c++) {
					if(c+1 == C[i] || c+1 == C[v]) continue;
					cnt[(1<<c) | (1<<(C[v]-1))] += D[v][c+1];
				}
			}

			for(auto &p : KV[C[i]-1]) {
				Ans += cnt[p.first] * cnt[p.second] * 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));
	else if(4 == K) printf("%lld\n", kis4::run(N, M, A, B, C));
	else if(5 == K) printf("%lld\n", kis5::run(N, M, A, B, C));

	return 0;
}

Subtask #1
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	16760 KB	Output is correct
2	Correct	20 ms	16868 KB	Output is correct
3	Correct	19 ms	16944 KB	Output is correct
4	Correct	15 ms	16980 KB	Output is correct
5	Correct	16 ms	17056 KB	Output is correct
6	Correct	17 ms	17056 KB	Output is correct
7	Correct	14 ms	17072 KB	Output is correct
8	Correct	14 ms	17072 KB	Output is correct
9	Correct	19 ms	17084 KB	Output is correct
10	Correct	15 ms	17084 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	147 ms	23108 KB	Output is correct
2	Correct	87 ms	23108 KB	Output is correct
3	Correct	382 ms	28908 KB	Output is correct
4	Correct	129 ms	28908 KB	Output is correct
5	Correct	100 ms	28908 KB	Output is correct
6	Correct	372 ms	28908 KB	Output is correct
7	Correct	380 ms	29096 KB	Output is correct
8	Correct	413 ms	29548 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	16760 KB	Output is correct
2	Correct	20 ms	16868 KB	Output is correct
3	Correct	19 ms	16944 KB	Output is correct
4	Correct	15 ms	16980 KB	Output is correct
5	Correct	16 ms	17056 KB	Output is correct
6	Correct	17 ms	17056 KB	Output is correct
7	Correct	14 ms	17072 KB	Output is correct
8	Correct	14 ms	17072 KB	Output is correct
9	Correct	19 ms	17084 KB	Output is correct
10	Correct	15 ms	17084 KB	Output is correct
11	Correct	147 ms	23108 KB	Output is correct
12	Correct	87 ms	23108 KB	Output is correct
13	Correct	382 ms	28908 KB	Output is correct
14	Correct	129 ms	28908 KB	Output is correct
15	Correct	100 ms	28908 KB	Output is correct
16	Correct	372 ms	28908 KB	Output is correct
17	Correct	380 ms	29096 KB	Output is correct
18	Correct	413 ms	29548 KB	Output is correct
19	Correct	129 ms	29548 KB	Output is correct
20	Correct	106 ms	29548 KB	Output is correct
21	Correct	415 ms	29548 KB	Output is correct
22	Correct	115 ms	29548 KB	Output is correct
23	Correct	100 ms	29548 KB	Output is correct
24	Correct	271 ms	29548 KB	Output is correct
25	Correct	340 ms	29548 KB	Output is correct
26	Correct	405 ms	29752 KB	Output is correct
27	Correct	147 ms	29752 KB	Output is correct
28	Correct	173 ms	29752 KB	Output is correct
29	Correct	699 ms	44596 KB	Output is correct
30	Correct	474 ms	44596 KB	Output is correct
31	Correct	483 ms	44596 KB	Output is correct
32	Correct	681 ms	44716 KB	Output is correct
33	Correct	18 ms	44716 KB	Output is correct
34	Correct	16 ms	44716 KB	Output is correct
35	Correct	21 ms	44716 KB	Output is correct
36	Correct	21 ms	44716 KB	Output is correct
37	Correct	19 ms	44716 KB	Output is correct
38	Correct	22 ms	44716 KB	Output is correct
39	Correct	22 ms	44716 KB	Output is correct
40	Correct	20 ms	44716 KB	Output is correct
41	Correct	18 ms	44716 KB	Output is correct
42	Correct	20 ms	44716 KB	Output is correct

Subtask #4
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	44716 KB	Output is correct
2	Correct	66 ms	44716 KB	Output is correct
3	Correct	44 ms	44716 KB	Output is correct
4	Correct	101 ms	44716 KB	Output is correct
5	Correct	77 ms	44716 KB	Output is correct
6	Correct	239 ms	44716 KB	Output is correct
7	Correct	47 ms	44716 KB	Output is correct
8	Correct	131 ms	44716 KB	Output is correct
9	Correct	115 ms	44716 KB	Output is correct
10	Correct	148 ms	44716 KB	Output is correct
11	Correct	157 ms	44716 KB	Output is correct
12	Correct	117 ms	44716 KB	Output is correct
13	Correct	147 ms	44716 KB	Output is correct
14	Correct	265 ms	44716 KB	Output is correct
15	Correct	255 ms	44716 KB	Output is correct
16	Correct	22 ms	44716 KB	Output is correct
17	Correct	19 ms	44716 KB	Output is correct
18	Correct	17 ms	44716 KB	Output is correct
19	Correct	19 ms	44716 KB	Output is correct
20	Correct	23 ms	44716 KB	Output is correct
21	Correct	16 ms	44716 KB	Output is correct
22	Correct	22 ms	44716 KB	Output is correct
23	Correct	22 ms	44716 KB	Output is correct
24	Correct	21 ms	44716 KB	Output is correct
25	Correct	20 ms	44716 KB	Output is correct

답안 #63182

Compilation message

Subtask #1 23.0 / 23.0

Subtask #2 20.0 / 20.0

Subtask #3 27.0 / 27.0

Subtask #4 30.0 / 30.0

Subtask #1
23.0 / 23.0

Subtask #2
20.0 / 20.0

Subtask #3
27.0 / 27.0

Subtask #4
30.0 / 30.0