Submission #1184830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184830		Unforgettablepl	Amusement Park (CEOI19_amusementpark)	C++20	7 / 100	0 ms	328 KiB

amusementpark

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int modulo = 998244353;
const int div2 = 499122177;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin >> n >> m;
    vector<vector<int>> adj(n+1);
    vector<pair<int,int>> edges(m+1);
    for(int i=1;i<=m;i++){
        int a,b;
        cin >> a >> b;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
        edges.emplace_back(a,b);
    }
    vector<int> par(n+1);
    vector<vector<int>> cleanadj(n+1);
    vector<bool> visited(n+1);
    vector<int> depth(n+1);
    // TEMP
    vector<pair<int,int>> backedges(n+1);
    // TEMP END
    {   
        function<void(int,int,int)> dfs = [&](int x,int p,int dep){
            par[x]=p;
            visited[x]=true;
            depth[x]=dep;
            for(int&i:adj[x])if(i!=p){
                if(visited[i]){
                    if(depth[i]<depth[x]){
                        backedges.emplace_back(i,x);
                    }
                } else {
                    dfs(i,x,dep+1);
                    cleanadj[x].emplace_back(i);
                }
            }
        };
        for(int i=1;i<=n;i++)if(!visited[i])dfs(i,0,0);
    }
    vector<bool> picked(n+1);
    vector<int> pre(n+1);
    function<void(int,int)> dfs = [&](int x,int curr){
        visited[x]=true;
        if(picked[x])curr++;
        pre[x]=curr;
        for(int&i:cleanadj[x])dfs(i,curr);
    };
    int ans = 0;
    for(int mask = 0;mask<(1<<n);mask++){
        bool works = true;
        for(int i=0;i<n;i++){
            if(mask&(1<<i) and par[i+1]==0)works=false;
            else if(mask&(1<<i))picked[i+1]=true;
            else picked[i+1]=false;
        }
        if(!works)continue;
        int curr = 1;
        fill(visited.begin(),visited.end(),false);
        for(int i=1;i<n;i++)if(!visited[i])dfs(i,0);
        for(auto&[a,b]:backedges){
            if(pre[b]-pre[a]!=depth[b]-depth[a] and pre[b]-pre[a]!=0){
                curr*=2;
                curr%=modulo;
            }
        }
        ans+=curr;
        ans%=modulo;
    }
    cout << (((ans*m)%modulo)*div2)%modulo << '\n';
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 23
• Subtask 4: 0 / 21
• Subtask 5: 0 / 37