Submission #1096326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096326		vjudge1	The Xana coup (BOI21_xanadu)	C++11	0 / 100	1085 ms	82340 KiB

xanadu

#include <bits/stdc++.h>
#define int long long
#define prr pair<int,int>
using namespace std;
map<int,bool>vis;
struct node{
    int nxt,to;
}e[114514];
int tot=0,head[114514],n,b[100001];
void add(int x,int y){
    e[++tot].nxt=head[x];
    e[tot].to=y;
    head[x]=tot;
}

signed main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        add(x,y);add(y,x);
    }
    int r=0;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        r=r+(x<<(i-1));
    }
    priority_queue<prr,vector<prr>,greater<prr> >q;
    q.push(make_pair(0,r));
    while(!q.empty()){
        int step=q.top().first,cur=q.top().second;
        q.pop();
        if(cur==0){
            cout<<step<<endl;
            return 0;
        }
        if(vis[cur])continue;
        vis[cur]=true;
        
        for(int i=1;i<=n;i++)b[i]=(!!((1<<(i-1))&cur));
        for(int i=1;i<=n;i++){
            b[i]=!b[i];
            for(int j=head[i];j;j=e[j].nxt){
                int to=e[j].to;
                b[to]=!b[to];
            }
            
            int r=0;
            for(int j=1;j<=n;j++){
                r+=(b[j]<<(j-1));
            }
            
            q.push(make_pair(step+1,r));
            b[i]=!b[i];
            for(int j=head[i];j;j=e[j].nxt){
                int to=e[j].to;
                b[to]=!b[to];
            }
        }
    }
    cout<<"impossible"<<endl;
    return 0;
}

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