# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
951978 | mocha | Paths (BOI18_paths) | C++14 | 83 ms | 30292 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
using namespace std;
const int mx = 3e5+5;
int n, m, k;
int cnt[1<<5][mx];
int tmp[1<<5][mx];
int c[mx];
vector<pair<int, int>> e;
int ans1, ans2, ans3, ans4, ans5;
vector<int> nums[6];
int ans;
void init() {
for (int i=0;i<1<<k;i++) {
int ii=i, cnt=0;
while (ii) {
cnt += (ii&1);
ii >>= 1;
}
nums[cnt].push_back(i);
}
}
void get1() {
for (auto [u, v]:e) {
cnt[c[v]][u]++;
cnt[c[u]][v]++;
}
for (int i=1;i<=n;i++) {
for (int j:nums[1]) {
if (j == c[i]) continue;
ans1 += cnt[j][i];
}
}
}
void get2() {
for (int i=1;i<=n;i++) {
for (int x = 1;x<1<<k;x<<=1) {
if (x == c[i]) continue;
for (int y = 1; y < 1<<k ; y<<=1) {
if ( y == c[i] or x == y) continue;
ans2 += cnt[x][i] * cnt[y][i];
}
}
}
}
void get3() {
for (auto [u, v]:e) {
if (c[u] == c[v]) continue;
for (int x = 1;x<1<<k;x<<=1) {
if (x == c[u] or x == c[v]) continue;
for (int y = 1; y < 1<<k ; y<<=1) {
if (y == c[u] or y == c[v] or x == y) continue;
ans2 += cnt[x][v] * cnt[y][u] * 2;
}
}
}
}
void get4() {}
signed main() {
cin.tie(0);ios::sync_with_stdio(0);
cin >> n >> m >> k;
e.resize(m);
init();
for (int i=1;i<=n;i++) {
int x;
cin >> x; x--;
c[i] = 1<<x;
}
for (int i=0;i<m;i++) {
cin >> e[i].ff >> e[i].ss;
}
if (k == 1) {
ans = 0;
} else if (k == 2) {
get1();
ans = ans1;
} else if (k == 3) {
get1(); get2();
ans = ans1 + ans2;
} else if (k == 4) {
get1(); get2(); get3();
ans = ans1 + ans2 + ans3;
}
cout << ans << "\n";
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |