# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
63173 |
2018-08-01T03:55:35 Z |
윤교준(#1834) |
Paths (BOI18_paths) |
C++11 |
|
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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
12 ms |
7416 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
12 ms |
7416 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
10 ms |
31788 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |