Submission #1106861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106861		hengliao	Plus Minus (BOI17_plusminus)	C++17	100 / 100	58 ms	8544 KiB

plusminus

#include <bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;

const ll mxN=1e5+5;
const ll mod=1e9+7;

vll con;

ll pw(ll a, ll b){
    a%=mod;
    ll re=1;
    for(ll i=0;i<63;i++){
        if(b&(1LL<<i)){
            re*=a;
            re%=mod;
        }
        a*=a;
        a%=mod;
    }
    return re;
}

ll id(ll tar){
    return lower_bound(con.begin(), con.end(), tar)-con.begin();
}

ll x[mxN];
ll y[mxN];
ll flag[mxN];
bool bad=0;
ll state[2*mxN];
ll sz;

void solve(){
	ll n, m, k;
    cin>>n>>m>>k;
    for(ll i=0;i<k;i++){
        char c;
        cin>>c;
        if(c=='+') flag[i]=1;
        else flag[i]=-1;
        cin>>x[i]>>y[i];
        con.pb(x[i]);
        con.pb(y[i]);
    }
    sort(con.begin(), con.end());
    con.erase(unique(con.begin(), con.end()), con.end());
    sz=con.size();
    for(ll i=0;i<sz;i++){
        state[i]=0;
    }
    bad=0;
    auto f=[&](ll idx, ll flg){
        if(idx%2==0){
            return -flg;// test
        }
        else{
            return flg;
        }
    };
    for(ll i=0;i<k;i++){
        ll re=f(x[i], flag[i]);
        if(state[id(y[i])]==0){
            state[id(y[i])]=re;
        }
        else if(state[id(y[i])]!=re){
            bad=1;
        }
    }
    ll ans=0;
    if(!bad){
        ll tep=m;
        for(ll i=0;i<sz;i++){
            if(state[i]!=0) tep--;
        }
        ans+=pw(2, tep);
        ll tep2=0;
        bool bad2=0;
        for(ll i=0;i<sz;i++){
            if(state[i]!=0){
                ll re=f(con[i], state[i]);
                if(tep2==0){
                    tep2=re;
                }
                else if(tep2!=re){
                    bad2=1;
                }
            }
        }
        if(!bad2){
            ans--;
            if(k==0) ans--;
            if(ans<0) ans+=mod;
        }
    }
    for(ll i=0;i<sz;i++){
        state[i]=0;
    }
    bad=0;
    for(ll i=0;i<k;i++){
        ll re=f(y[i], flag[i]);
        if(state[id(x[i])]==0){
            state[id(x[i])]=re;
        }
        else if(state[id(x[i])]!=re){
            bad=1;
        }
    }
    if(!bad){
        ll tep=n;
        for(ll i=0;i<sz;i++){
            if(state[i]!=0) tep--;
        }
        ans+=pw(2, tep);
        ans%=mod;
    }
    
    cout<<ans<<'\n';
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

	solve();
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 42 / 42
• Subtask 3: 46 / 46