oj.uz

Submission #658572

# Submission time Handle Problem Language Result Execution time Memory
658572 2022-11-13T14:45:52 Z joelgun14 Paths (BOI18_paths) C++17
100 / 100
 753 ms 24720 KB 
// header file
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// pragma
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// macros
#define endl "\n"
#define ll long long
#define mp make_pair
#define ins insert
#define lb lower_bound
#define pb push_back
#define ub upper_bound
#define lll __int128
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
bool used[5];
vector<int> avail, cur;
vector<vector<int>> combi;
void generate_combi(int n, int idx) {
    if(idx == n) {
        combi.pb(cur);
    }
    for(int i = 0; i < avail.size(); ++i) {
        if(!used[i]) {
            used[i] = 1;
            cur.pb(avail[i]);
            generate_combi(n, idx + 1);
            cur.pop_back();
            used[i] = 0;
        }
    }
}
void generate(int n) {
    for(int i = 1; i <= n; ++i)
        avail.pb(i);
    for(int i = 2; i <= n; ++i) {
        generate_combi(i, 0);
    }
}
const int lim = 3e5 + 5;
int color[lim];
vector<int> edges[lim];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    // obs:
    // each edge is only used once
    // each vertex is only used once
    // max path is amount of unique
    // try each permutation?
    int n, m, k;
    cin >> n >> m >> k;
    // try each permutation/combination of colors
    vector<int> tmp2;
    for(int i = 1; i <= k; ++i)
        tmp2.pb(i);
    generate(k);
    for(int i = 1; i <= n; ++i)
        cin >> color[i];
    for(int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        edges[u].pb(v);
        edges[v].pb(u);
    }
    ll res = 0;
    for(auto arr : combi) {
        //for(auto i : arr)
        //    cout << i << " ";
        //cout << endl;
        // fi fi nd fi se pr se idx
        queue<pair<pair<int, int>, int>> bfs;
        int ways[n + 1];
        bool vis[n + 1];
        memset(vis, 0, sizeof(vis));
        memset(ways, 0, sizeof(ways));
        for(int i = 1; i <= n; ++i) {
            if(arr[0] == color[i])
                bfs.push(mp(mp(i, 0), 1)), ways[i] = 1;
        }
        while(bfs.size()) {
            int nd = bfs.front().fi.fi, pr = bfs.front().fi.se, idx = bfs.front().se;
            bfs.pop();
            if(idx == arr.size()) {
                res += ways[pr];
                continue;
            }
            ways[nd] += ways[pr];
            if(vis[nd])
                continue;
            vis[nd] = 1;
            for(auto i : edges[nd]) {
                if(arr[idx] == color[i]) {
                    bfs.push(mp(mp(i, nd), idx + 1));
                }
            }
        }
        //cout << res << endl;
    }    
    cout << res << endl;
    return 0;
}

Compilation message

paths.cpp: In function 'void generate_combi(int, int)':
paths.cpp:29:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i = 0; i < avail.size(); ++i) {
      |                    ~~^~~~~~~~~~~~~~
paths.cpp: In function 'int main()':
paths.cpp:89:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             if(idx == arr.size()) {
      |                ~~~~^~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7360 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 6 ms 7252 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 6 ms 7288 KB Output is correct
6 Correct 5 ms 7328 KB Output is correct
7 Correct 4 ms 7368 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7252 KB Output is correct
10 Correct 4 ms 7252 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 15136 KB Output is correct
2 Correct 85 ms 14500 KB Output is correct
3 Correct 317 ms 24108 KB Output is correct
4 Correct 88 ms 17276 KB Output is correct
5 Correct 90 ms 15168 KB Output is correct
6 Correct 217 ms 22168 KB Output is correct
7 Correct 300 ms 24020 KB Output is correct
8 Correct 323 ms 24720 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7360 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 6 ms 7252 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 6 ms 7288 KB Output is correct
6 Correct 5 ms 7328 KB Output is correct
7 Correct 4 ms 7368 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7252 KB Output is correct
10 Correct 4 ms 7252 KB Output is correct
11 Correct 87 ms 15136 KB Output is correct
12 Correct 85 ms 14500 KB Output is correct
13 Correct 317 ms 24108 KB Output is correct
14 Correct 88 ms 17276 KB Output is correct
15 Correct 90 ms 15168 KB Output is correct
16 Correct 217 ms 22168 KB Output is correct
17 Correct 300 ms 24020 KB Output is correct
18 Correct 323 ms 24720 KB Output is correct
19 Correct 91 ms 15124 KB Output is correct
20 Correct 80 ms 14528 KB Output is correct
21 Correct 304 ms 24024 KB Output is correct
22 Correct 87 ms 17232 KB Output is correct
23 Correct 102 ms 15240 KB Output is correct
24 Correct 215 ms 22176 KB Output is correct
25 Correct 312 ms 24256 KB Output is correct
26 Correct 321 ms 24720 KB Output is correct
27 Correct 157 ms 13840 KB Output is correct
28 Correct 193 ms 15672 KB Output is correct
29 Correct 753 ms 23756 KB Output is correct
30 Correct 484 ms 19648 KB Output is correct
31 Correct 489 ms 19936 KB Output is correct
32 Correct 729 ms 23856 KB Output is correct
33 Correct 4 ms 7364 KB Output is correct
34 Correct 4 ms 7304 KB Output is correct
35 Correct 4 ms 7380 KB Output is correct
36 Correct 4 ms 7276 KB Output is correct
37 Correct 4 ms 7380 KB Output is correct
38 Correct 4 ms 7372 KB Output is correct
39 Correct 4 ms 7380 KB Output is correct
40 Correct 4 ms 7368 KB Output is correct
41 Correct 4 ms 7380 KB Output is correct
42 Correct 5 ms 7252 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 203 ms 9368 KB Output is correct
3 Correct 27 ms 9632 KB Output is correct
4 Correct 71 ms 12748 KB Output is correct
5 Correct 83 ms 13912 KB Output is correct
6 Correct 536 ms 12708 KB Output is correct
7 Correct 58 ms 9432 KB Output is correct
8 Correct 158 ms 12784 KB Output is correct
9 Correct 111 ms 13736 KB Output is correct
10 Correct 194 ms 13808 KB Output is correct
11 Correct 345 ms 11032 KB Output is correct
12 Correct 286 ms 12792 KB Output is correct
13 Correct 322 ms 11344 KB Output is correct
14 Correct 563 ms 12772 KB Output is correct
15 Correct 549 ms 12732 KB Output is correct
16 Correct 4 ms 7252 KB Output is correct
17 Correct 4 ms 7380 KB Output is correct
18 Correct 4 ms 7252 KB Output is correct
19 Correct 4 ms 7368 KB Output is correct
20 Correct 4 ms 7252 KB Output is correct
21 Correct 5 ms 7380 KB Output is correct
22 Correct 4 ms 7380 KB Output is correct
23 Correct 4 ms 7252 KB Output is correct
24 Correct 4 ms 7372 KB Output is correct
25 Correct 4 ms 7252 KB Output is correct