oj.uz

Submission #498686

# Submission time Handle Problem Language Result Execution time Memory
498686 2021-12-26T06:50:29 Z LittleCube Paths (BOI18_paths) C++14
100 / 100
 285 ms 33732 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

ll N, M, K, color[300005], adj[300005][6], adj2[100005][33];
pii edge[300005];
ll ans;

int encode(int i)
{
    return (1 << (i - 1));
}

signed main()
{
    //ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M >> K;
    for (int i = 1; i <= N; i++)
        cin >> color[i];
    for (int i = 1; i <= M; i++)
        cin >> edge[i].F >> edge[i].S;
    if (K >= 2)
    {
        for (int i = 1; i <= M; i++)
            if (color[edge[i].F] != color[edge[i].S])
                ans += 2;
    }
    cerr << ans << '\n';
    if (K >= 3)
    {
        for (int i = 1; i <= M; i++)
            if (color[edge[i].F] != color[edge[i].S])
            {
                adj[edge[i].F][color[edge[i].S]]++;
                adj[edge[i].S][color[edge[i].F]]++;
            }
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= K; j++)
                for (int k = j + 1; k <= K; k++)
                    ans += adj[i][j] * adj[i][k] * 2;
    }
    cerr << ans << '\n';
    if (K >= 4)
    {
        for (int i = 1; i <= M; i++)
            if (color[edge[i].F] != color[edge[i].S])
                for (int j = 1; j <= K; j++)
                    for (int k = 1; k <= K; k++)
                        if (j != k && color[edge[i].F] != k && color[edge[i].S] != j)
                            ans += adj[edge[i].F][j] * adj[edge[i].S][k] * 2;
    }
    cerr << ans << '\n';
    if (K >= 5)
    {
        for (int i = 1; i <= M; i++)
            if (color[edge[i].F] != color[edge[i].S])
            {
                for (int j = 1; j <= K; j++)
                    if (color[edge[i].F] != j)
                        adj2[edge[i].F][encode(color[edge[i].F]) ^ encode(color[edge[i].S]) ^ encode(j)] += adj[edge[i].S][j];
                for (int j = 1; j <= K; j++)
                    if (color[edge[i].S] != j)
                        adj2[edge[i].S][encode(color[edge[i].F]) ^ encode(color[edge[i].S]) ^ encode(j)] += adj[edge[i].F][j];
            }
       
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= K; j++)
                if (j != color[i])
                    for (int k = j + 1; k <= K; k++)
                        if (k != color[i])
                        {
                            ans += adj2[i][encode(color[i]) ^ encode(j) ^ encode(k)] * adj2[i][31 ^ encode(j) ^ encode(k)];
                        }
    }
    cout << ans << '\n';
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 2892 KB Output is correct
2 Correct 124 ms 2576 KB Output is correct
3 Correct 223 ms 19036 KB Output is correct
4 Correct 160 ms 2760 KB Output is correct
5 Correct 145 ms 2928 KB Output is correct
6 Correct 236 ms 13612 KB Output is correct
7 Correct 227 ms 18996 KB Output is correct
8 Correct 217 ms 18984 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 138 ms 2892 KB Output is correct
12 Correct 124 ms 2576 KB Output is correct
13 Correct 223 ms 19036 KB Output is correct
14 Correct 160 ms 2760 KB Output is correct
15 Correct 145 ms 2928 KB Output is correct
16 Correct 236 ms 13612 KB Output is correct
17 Correct 227 ms 18996 KB Output is correct
18 Correct 217 ms 18984 KB Output is correct
19 Correct 134 ms 2872 KB Output is correct
20 Correct 125 ms 2664 KB Output is correct
21 Correct 222 ms 19028 KB Output is correct
22 Correct 156 ms 2756 KB Output is correct
23 Correct 142 ms 2784 KB Output is correct
24 Correct 209 ms 13544 KB Output is correct
25 Correct 225 ms 18984 KB Output is correct
26 Correct 228 ms 19040 KB Output is correct
27 Correct 147 ms 2668 KB Output is correct
28 Correct 148 ms 3016 KB Output is correct
29 Correct 285 ms 19012 KB Output is correct
30 Correct 218 ms 10824 KB Output is correct
31 Correct 209 ms 10864 KB Output is correct
32 Correct 265 ms 19012 KB Output is correct
33 Correct 0 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 0 ms 204 KB Output is correct
36 Correct 0 ms 204 KB Output is correct
37 Correct 1 ms 204 KB Output is correct
38 Correct 0 ms 204 KB Output is correct
39 Correct 0 ms 204 KB Output is correct
40 Correct 0 ms 204 KB Output is correct
41 Correct 0 ms 204 KB Output is correct
42 Correct 1 ms 204 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 48 ms 1220 KB Output is correct
3 Correct 37 ms 1832 KB Output is correct
4 Correct 70 ms 7880 KB Output is correct
5 Correct 69 ms 7804 KB Output is correct
6 Correct 118 ms 33732 KB Output is correct
7 Correct 43 ms 1812 KB Output is correct
8 Correct 73 ms 7880 KB Output is correct
9 Correct 78 ms 7844 KB Output is correct
10 Correct 82 ms 7916 KB Output is correct
11 Correct 89 ms 17716 KB Output is correct
12 Correct 119 ms 25848 KB Output is correct
13 Correct 81 ms 17832 KB Output is correct
14 Correct 114 ms 33724 KB Output is correct
15 Correct 116 ms 33652 KB Output is correct
16 Correct 1 ms 208 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 1 ms 208 KB Output is correct
20 Correct 1 ms 208 KB Output is correct
21 Correct 1 ms 308 KB Output is correct
22 Correct 1 ms 208 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 0 ms 216 KB Output is correct
25 Correct 0 ms 208 KB Output is correct