Submission #1126370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126370		AverageAmogusEnjoyer	Paths (BOI18_paths)	C++20	23 / 100	3094 ms	4164 KiB

paths

    #pragma GCC optimize("O3,unroll-loops")
    #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
    #include <bits/stdc++.h>
    using namespace std;
    using ll = long long;
    template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
    template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }

    mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> ui(0, 1 << 30);

    int rng() { 
        return ui(mrand);
    }

    int main() {
        ios_base::sync_with_stdio(false); 
        cin.tie(nullptr);
        
        int n,m,k;
        cin >> n >> m >> k;
        vector<int> a(n);
        for (int &x: a) {
            cin >> x;
        }
        vector<vector<int>> adj(n);
        for (int u,v;m--;) {
            cin >> u >> v;
            --u,--v;
            adj[u].push_back(v),adj[v].push_back(u);
        }
        auto dfs = [&](auto &self,int u,int mask)->ll {
            if ((mask >> a[u]) & 1) return 0;
            ll res = (mask > 0);
            mask |= 1 << a[u];
            for (int &v: adj[u]) 
                res += self(self,v,mask);
            return res; 
        };
        ll ans = 0;
        for (int i=0;i<n;i++) {
            ans += dfs(dfs,i,0);
        }
        cout << ans << "\n";
    }

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