oj.uz

Submission #866410

# Submission time Handle Problem Language Result Execution time Memory
866410 2023-10-26T05:18:16 Z The_Samurai Paths (BOI18_paths) C++17
23 / 100
 3000 ms 7004 KB 
//#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.0 / 23.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3053 ms 7004 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Execution timed out 3053 ms 7004 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 3067 ms 2296 KB Time limit exceeded
3 Halted 0 ms 0 KB -