oj.uz

Submission #498679

# Submission time Handle Problem Language Result Execution time Memory
498679 2021-12-26T06:27:53 Z LittleCube Paths (BOI18_paths) C++14
23 / 100
 84 ms 14096 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;

int N, M, K, color[300005], adj[300005][5];
pii edge[300005];
ll ans;

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;
    }
    cout << ans << '\n';
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 5540 KB Output is correct
2 Correct 42 ms 4932 KB Output is correct
3 Correct 75 ms 14096 KB Output is correct
4 Correct 49 ms 6132 KB Output is correct
5 Correct 44 ms 6076 KB Output is correct
6 Incorrect 84 ms 11416 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 44 ms 5540 KB Output is correct
12 Correct 42 ms 4932 KB Output is correct
13 Correct 75 ms 14096 KB Output is correct
14 Correct 49 ms 6132 KB Output is correct
15 Correct 44 ms 6076 KB Output is correct
16 Incorrect 84 ms 11416 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Incorrect 20 ms 1800 KB Output isn't correct
3 Halted 0 ms 0 KB -