제출 #1184834

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1184834		Unforgettablepl	Amusement Park (CEOI19_amusementpark)	C++20	19 / 100	3095 ms	436 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<pair<int,int>> edges;
    for(int i=1;i<=m;i++){
        int a,b;
        cin >> a >> b;
        edges.emplace_back(a,b);
    }
    int ans = 0;
    for(int mask = 0;mask<(1<<m);mask++){
        bool works = true;
        int curr = 0;
        vector<vector<int>> adj(n+1);
        for(int i=0;i<m;i++){
            if(mask&(1<<i))adj[edges[i].first].emplace_back(edges[i].second);
            else {
                adj[edges[i].second].emplace_back(edges[i].first);
                curr++;
            }
        }
        vector<int> visited(n+1);
        function<void(int)> dfs = [&](int x){
            if(visited[x]){
                if(visited[x]==1)works=false;
                return;
            }
            visited[x]=1;
            for(int&i:adj[x])dfs(i);
            visited[x]=2;
        };
        for(int i=1;i<=n;i++)dfs(i);
        if(!works)continue;
        ans++;
    }
    cout << ans/2 * m << '\n';
}

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