Submission #1008603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008603		cow123	Newspapers (CEOI21_newspapers)	C++14	12 / 100	2822 ms	524288 KiB

newspapers

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i = a; i < b;++i)
#define pb emplace_back
#define mp make_pair
#define f first
#define s second
using namespace std;
const int maxn = 1005,wiel = (1 << 22) + 5;
vector<int> V[maxn];
vector<pair<int,int>> V1[wiel];
int vis[wiel],from[wiel],kraw[wiel],to[wiel];
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n,m;
    cin>>n >>m;
    FOR(i,0,m){
        int x,y;
        cin>>x >>y;
        V[x].pb(y);
        V[y].pb(x);
    }
    FOR(i,0,(1 << n)){
        FOR(j,0,n){
            if((i & (1 << j))){
                int x = i - (1 << j);
                V1[i].pb(mp(x,j));
            }
        }
    }
    FOR(i,0,(1 << n)){
        int vis1[n + 1];
        FOR(j,0,n + 1){vis1[j] = 0;}
        FOR(j,0,n){
            if(i & (1 << j)){
                for(auto y : V[j + 1]){
                    vis1[y] = 1;
                }
            }
        }
        int suma = 0;
        FOR(j,1,n + 1){
            if(vis1[j] == 1){
                suma+=(1 << (j - 1));
            }
        }
        to[i] = suma;
    }
    
    vis[(1 << n) - 1] = 1;
    
    queue<int> Q;
    Q.push((1 << n) - 1);
    while(!Q.empty()){
        auto x = Q.front();
        Q.pop();
        for(auto &y : V1[x]){
            if(vis[to[y.f]] == 0){
                vis[to[y.f]] = vis[x] + 1;
                from[to[y.f]] = x;
                kraw[to[y.f]] = y.s;
                Q.push(to[y.f]);
            }
        }
    }
    if(vis[0] == 0){
        cout<<"NO";
        return 0;
    }else{
        cout<<"YES" <<"\n" <<vis[0] - 1 <<"\n"; 
        int x = 0;
        vector<int> ans;
        while(x != ((1 << n) - 1)){
            ans.pb(kraw[x]);
            x = from[x];
        }
        reverse(ans.begin(),ans.end());
        FOR(i,0,vis[0] - 1){
            cout<<ans[i] + 1;
            if(i != vis[0] - 2){
                cout<<" ";
            }
        }
    }
}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 8
• Subtask 3: 0 / 80