Submission #866410

#	Time	Username	Problem	Language	Result	Execution time	Memory
866410		The_Samurai	Paths (BOI18_paths)	C++17	23 / 100	3067 ms	7004 KiB

paths

//#pragma GCC optimize("O3", "unroll-loops")
//#pragma GCC target("avx2", "popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll inf = 1e18;

vector<int> col_v;
vector<bool> vis, color;
vector<vector<int>> g;
int cnt;
ll ans;

void dfs(int u) {
    if (color[col_v[u]]) return;
    cnt++;
    vis[u] = true;
    color[col_v[u]] = true;
    if (cnt > 1) ans++;
    for (int v: g[u]) {
        if (vis[v]) continue;
        dfs(v);
    }
    cnt--;
    vis[u] = false;
    color[col_v[u]] = false;
}

int main() {
    srand(time(0));
    cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int n, m, k;
    cin >> n >> m >> k;
    col_v.assign(n + 1, 0);
    g.assign(n + 1, {});
    for (int i = 1; i <= n; i++) cin >> col_v[i];
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    vis.assign(n + 1, false);
    color.assign(k + 1, false);
    for (int i = 1; i <= n; i++) dfs(i);
    cout << ans;

}

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