Submission #1115875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115875		flyingkite	Plus Minus (BOI17_plusminus)	C++17	0 / 100	1 ms	336 KiB

plusminus

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
 
const ll N = 1e6 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 1e3;
ll n,m,k,cc;
map<ll,vector<ll>>mp;
map<ll,ll>p, sz;
ll find(ll u){return (u == p[u]) ? u : p[u] = find(p[u]);}
void join(ll u, ll v){
    u = find(u), v = find(v);
    if(u == v) return;
    if(sz[u] < sz[v]) swap(u, v);
    p[v] = u; sz[u] += sz[v];
    cc--;
}
ll bpow(ll a, ll b){
    if(b == 0) return 1;
    ll ans = bpow(a, b / 2);
    if(b % 2) return ans * ans % mod * a % mod;
    else return ans * ans % mod;
}
void to_thic_cau(){
    cin >> n >> m >> k;
    for(int i = 1; i <= k;i++){
        char c; ll x,y; cin >> c >> x >> y;
        mp[y].pb(x); p[y] = y; sz[y] = 1;
    }
    cc = n;
    for(auto vec : mp){
        ll lst = -1;
        for(auto x : vec.S){
            if(lst != -1) join(lst, x);
            lst = x;
        }
    }
    ll rem = m - mp.size() - 1;
    if(rem == -1) rem = mod - 2;
    cout << bpow(2, cc) * bpow(2, rem) % mod << '\n';
}

signed main()
{   
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tc = 1;   
    //cin >> tc;
    while(tc--) to_thic_cau();
}

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