제출 #1220839

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1220839		Trumling	Amusement Park (CEOI19_amusementpark)	C++20	19 / 100	3093 ms	436 KiB

amusementpark

//Trumling ©
//Αφόδευε υψηλά και ηγνάντει 
#include <bits/stdc++.h>
using namespace std; 

typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 998244353
#define all(x) x.begin(),x.end()

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);

ll n,m;
cin>>n>>m;

pair<ll,ll> arr[m];
vector<vector<bool>>g(n+1,vector<bool>(n+1,0));
for(int i=0;i<m;i++)
    {
        cin>>arr[i].F>>arr[i].S;
        g[arr[i].F][arr[i].S]=1;
    }

ll ans=0;
for(int i=0;i<(1<<m);i++)
{
    ll cost=0;
    for(int j=0;j<m;j++)
        if(i&(1<<j))
            {
                cost++;
                g[arr[j].F][arr[j].S]=0;
                g[arr[j].S][arr[j].F]=1;
            }
    
    queue<ll>q;
    vector<bool>vis(n+1,0);
    bool tf=1;

    for(int j=1;j<=n;j++)
        if(!vis[j])
            {
                vis[j]=1;
                q.push(j);
                while(!q.empty())
                {
                    ll curr=q.front();
                    q.pop();
                    
                    for(int ii=1;ii<=n;ii++)
                        if(g[curr][ii] && !vis[ii])
                            {
                                vis[ii]=1;
                                q.push(ii);
                            }
                        else if(vis[ii] && g[curr][ii])
                        {
                            //cout<<i<<','<<curr<<','<<ii<<'\n';
                            vector<bool>vis2(n+1,0);
                            queue<ll>q2;
                            vis2[ii]=1;
                            q2.push(ii);
                            while(!q2.empty())
                            {
                                ll curr2=q2.front();
                                q2.pop();
                                for(int jj=1;jj<=n;jj++)
                                    if(g[curr2][jj] && !vis2[jj])
                                        {
                                            vis2[jj]=1;
                                            q2.push(jj);
                                        }
                            }
                            if(vis2[curr])
                                {
                                   // cout<<curr;
                                    tf=0;
                                    break;
                                }
                        }
                    if(!tf)
                        break;
                }

                if(!tf)
                    break;
            }
    if(tf)
        ans+=cost;

    for(int j=0;j<m;j++)
        if(i&(1<<j))
            {
                g[arr[j].F][arr[j].S]=1;
                g[arr[j].S][arr[j].F]=0;
            }
        
}
cout<<ans;
}

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