Submission #1294147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294147		krzyska	Paths (BOI18_paths)	C++20	23 / 100	3095 ms	4248 KiB

paths

#include <bits/stdc++.h>
using namespace std;
int n, k;
int kolor[300005];
bool odw[300005];
vector<int> graf[300005];
unsigned long long wyn{};

void brut_force(int v, bitset<5> szet) {
    szet[kolor[v] - 1] = 1;
    if (szet[0] + szet[1] + szet[2] + szet[3] + szet[4] > 1) {
        wyn++;
    }

    for (auto i:graf[v]) {
        if (!szet[kolor[i] - 1]) {
            brut_force(i, szet);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int m, a, b;
    cin >> n >> m >> k;

    for (int i = 1; i <= n; i++) {
        cin >> kolor[i];
    }

    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }

    for (int i = 1; i <= n; i++) {
        bitset<5> szit;
        for (int j = 0; j < 5; j++) {
            szit[j] = 0;
        }
        brut_force(i, szit);
    }

    cout << wyn;
}

• Subtask 1: 23 / 23
• Subtask 2: 0 / 20
• Subtask 3: 0 / 27
• Subtask 4: 0 / 30