Submission #1056748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056748		SzymonKrzywda	The Xana coup (BOI21_xanadu)	C++17	15 / 100	1088 ms	7268 KiB

xanadu

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,a,b;
    
    cin >> n;
    
    vector<vector<int>> graf(n, vector<int>(0));
    vector<int> tablica(n,0);
    
    bool sciezka = true;
    
    for (int i=0; i<n-1; i++){
        cin >> a >> b;
        a--;b--;
        graf[a].push_back(b);
        graf[b].push_back(a);
        if (abs(a-b)!=1) sciezka=false;
    }
    
    for (int i=0; i<n; i++) cin >> tablica[i];
    
    
    if (sciezka){
        int wynik=0;
        for (int i=1; i<n; i++){
            if (tablica[i-1]){
                tablica[i-1] = 0;
                tablica[i] = (tablica[i]+1)%2;
                if (i<(n-1)) tablica[i+1] = (tablica[i+1]+1)%2;
                wynik++;
            }
        }
        
        bool git=true;
        for (int i=0; i<n; i++) if(tablica[i]) git=false;
        
        if (git) cout << wynik << endl;
        else cout << "impossible\n";
        
    }
    else{
        vector<int> tablica_2(n,0);
        int wynik=1e7;
        for (int j=0; j<=((long long)1<<n); j++){

            int wynik_2=0;
            for (int i=0; i<n; i++) tablica_2[i] = tablica[i];
            
            for (int i=0; i<n; i++){
                //cout << j << " " << i <<" " << ((j)&(1<<(i))) << " " << (1<<(i)) << endl;
                if ((j)&((long long)1<<(i))){
                    tablica_2[i] = (tablica_2[i]+1)%2;
                    for (auto k : graf[i]) tablica_2[k] = (tablica_2[k]+1)%2;
                    wynik_2++;
   
                }
            }
            bool good = true;
            for (int i=0; i<n; i++){
                if (tablica_2[i]) {good=false; break;}
            }

            if (good) {
                wynik = min(wynik,wynik_2);
                //for (int i=0; i<n; i++){
                //if ((j)&(1<<(i))){
            }
            
        }
        if (wynik==1e7) cout << "impossible\n";
        else cout << wynik << endl;
        
    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 15
• Subtask 3: 10 / 10
• Subtask 4: 0 / 40
• Subtask 5: 0 / 30