Submission #1056848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056848		SzymonKrzywda	The Xana coup (BOI21_xanadu)	C++17	0 / 100	1071 ms	604 KiB

xanadu

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 40;


vector<vector<int>> graf(MAXN, vector<int>(0));
vector<int> tablica(MAXN,0);

int wynik=0;
void dfs(int v, int p){
    cout << "Wchodze: " << v << " " << p << endl;

    for (auto i : graf[v]){
        if (i!=p) dfs(i,v);
    }
    cout << "Wracam: " << v << " " << p << endl;
        for (auto i : tablica) cout << i << " ";
    cout << endl;
    
    if (graf[v].size()==1){
        if (tablica[v]){
            tablica[v] = 0;
            for (auto i : graf[v]) tablica[i] = (tablica[i]+1)%2;
            wynik++;
        }
    }
    else{
        bool git = true;
        for (auto i : graf[v]){
            if (i!=p && tablica[i]!=1) git = false;
        }
        if (git){
            tablica[v] = (tablica[v]+1)%2;
            for (auto i : graf[v]){
                tablica[i] = (tablica[i]+1)%2;
            }
            wynik++;
        }
    }
    
}


int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,a,b;
    
    cin >> n;
    

    
    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];
    
    priority_queue<pair<int,int>> kolejka;
    
    for (int i=0; i<n; i++){
        if (graf[i].size()==1 && tablica[i]) kolejka.push({2,i});
        else if (tablica[i]) kolejka.push({1,i});
    }
    
    
    vector<bool> odw(n,false);
    while (!kolejka.empty()){
        int v = kolejka.top().second;
        //cout << "V: "<< v << endl;
        kolejka.pop();
        
        bool pomin = true;
        if (tablica[v]) pomin=false;
        for (auto i : graf[v]){
            //cout << i << " " << tablica[i] << endl;
            if (tablica[i]) pomin=false;
        }
        if (pomin) continue;
        //cout << "DUPA\n";
        bool git=true;
        for (auto i : graf[v]){
            //cout << i << " " << git << endl;
            if (odw[i]&&(!tablica[i])) git=false;
        }
                //cout << "DUPA2\n";
        if (!git){
            for (auto i : graf[v]){
                //cout << "I " << i << " " << odw[i] << " " << kolejka.size() << endl;
                if (!odw[i]){
                    if (graf[i].size()==1) kolejka.push({2,i});
                    else kolejka.push({1,i});
                    //cout << kolejka.size() << endl;
                }
            }
            continue;
        }
                //cout << "DUPA3\n";
        wynik++;
        odw[v] = true;
        
        tablica[v] = (tablica[v]+1)%2;
        
        for (auto i : graf[v]){
            tablica[i] = (tablica[i]+1)%2;
            if (tablica[i] && (!odw[i])){
                if (graf[i].size()==1) kolejka.push({2,i});
                else kolejka.push({1,i});
            }
        }
    }
    
    
    
    cout << wynik << endl;
    //for (auto i : tablica) cout<< i << " ";

    return 0;
}

Compilation message (stderr)

xanadu.cpp: In function 'int main()':
xanadu.cpp:56:10: warning: variable 'sciezka' set but not used [-Wunused-but-set-variable]
   56 |     bool sciezka = true;
      |          ^~~~~~~

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