Submission #1121382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121382		RSAMSD	Plus Minus (BOI17_plusminus)	C++17	100 / 100	490 ms	55892 KiB

plusminus

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
int t = 0;
int const f = 2e5 + 10;
long long mod = 1e9 + 7;//998244353;
long long dp1[f][2];
long long dp2[f][2][2][2];
long long par[f];
long long a[f];
long long adj[f];
long long mmn =0;
pair<long long, long long> edges[f];
long long prefix[f];
vector<int>gc[f];
vector<int>gr[f];
struct node {
	long long val = 0;
	long long lazy = 0;
};
struct trpel {
	long long v, u, bank = 0;
};
node segtree[f * 8];
bool B[f];
void redany() {
	ifstream fin;
	ofstream fout;
	fin.open("std.in");
	fout.open("std.out");
}
void build(int v , int l , int r){
	if(r==l){
		segtree[v].val = 1e9;
		return;
	}
	int mid = (r+l)/2;
	build(2*v+1,mid+1,r);
	build(2*v,l,mid);
	segtree[v].val = max(segtree[v*2].val,segtree[2*v+1].val);
}
void upd(int v, int l, int r , int pos, int val){
	if(r==l&&r==pos){
		segtree[v].val = val;
		return;
	}
	int mid = (r+l)/2;
	if(pos>mid){
		upd(2*v+1,mid+1,r,pos,val);
	}
	else{
		upd(2*v,l,mid,pos,val);
	}
	segtree[v].val = max(segtree[v*2].val,segtree[2*v+1].val);
}
long long q(int v, int tl , int tr , int l ,int r){
	if(tl>r||tr<l)return 0;
	if(tr<=r&&tl>=l){
		return segtree[v].val;
	}
	int mid = (tr+tl)/2;
	return max(q(2*v,tl,mid,l,r),q(2*v+1,mid+1,tr,l,r));
}
// void merge(int a , int b, int n, int id){
	// if(g[a].size()>g[b].size()){
		// swap(a,b);
	// }
	// for(int u:g[a]){
		// if(u<n&&!B[u]&&par[u+1]==b){
			// upd(1,1,n,u,id);
			// B[u]=1;
		// }
		// if(u>1&&!B[u-1]&&par[u-1]==b){
			// upd(1,1,n,u-1,id);
			// B[u-1] =1;
		// }
		// g[b].push_back(u);
		// par[u] = b;
	// }
// }
long long powmod(long long a, long long p, long long modd) {
	long long ans = 1;
	while (p > 0) {
		if (p % 2 == 1) {
			ans *= a;
			ans %= modd;
			p--;
		}
		if (p == 0)break;
		a *= a;
		a %= modd;
		p /= 2;
	}
	return ans;
}
long long find(int v){
	while(par[v]!=v){
		v = par[v];
	}
	return v;
}
long long findx(int v){
	long long ans = 1;
	while(par[v]!=v){
		ans*=a[v];
		v = par[v];
	}
	return ans;
}
long long tw = powmod(2, mod - 2, mod);
int main() {
	ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	//cin >> t;
	t = 1;
	for (int hhh = 1;hhh <= t;hhh++) {
		long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 1, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
		string s1;
		string s3;
		char s2;
		long double dec = 0;
		bool c = 1;
		bool allrows =0;
		bool allculms =0;
		priority_queue<pair<long long, long long>> qq;
		multiset<long long> mul;
		queue<long long> pp;
		map<long long, long long> conv;
		map<long long,long long> convback;
		vector<long long> vec;
		cin >> n >> m>>k;
		for(int i =0;i<k;i++){
			cin>>s2>>r>>l;
			if(conv[r]==0){
				conv[r]= k2;
				convback[k2] = r;
				k2++;
				dp1[conv[r]][0] = 1;
				par[conv[r]] = conv[r];
			}
			if(conv[l+n]==0){
				conv[n+l]= k2;
				convback[k2]=l+n;
				B[k2]= 1;
				k2++;
				dp1[conv[l+n]][1] = 1;
				par[conv[l+n]] = conv[l+n];
			}
			if(s2=='+')d = 1;
			else d = -1;
			rr = find(conv[r]);
			ll = find(conv[l+n]);
			if(rr==ll){
				if(d!=findx(conv[r])*findx(conv[n+l])){
					c=0;
				}
			}
			else{
				d = d*findx(conv[r])*findx(conv[n+l]);
				if(dp1[rr][0]+dp1[rr][1]>dp1[ll][0]+dp1[ll][1]){
					par[ll] = rr;
					a[ll] = d;
					dp1[rr][0]+=dp1[ll][0];
					dp1[rr][1]+=dp1[ll][1];
				}
				else{
					par[rr] = ll;
					a[rr] = d;
					dp1[ll][0] += dp1[rr][0];
					dp1[ll][1]+=dp1[rr][1];
				}
			}
		}
		if(!c){
			cout<<0;
			break;
		}
		r=l=0;
		for(int i =1;i<k2;i++){
			rr = find(i);
			if(rr==i){
				mx++;
			}
			if(rr==i&&dp1[i][0]+dp1[i][1]>1){
					r+=dp1[i][0];
					l+=dp1[i][1];
			}
			if(!B[i]){
				if(findx(i)==1)
					dp2[rr][convback[i]%2][0][0] = 1;
				else
					dp2[rr][convback[i]%2][1][0] = 1;
				if((dp2[rr][convback[i]%2][0][0]==1&&dp2[rr][convback[i]%2][1][0]==1)||
				(dp2[rr][convback[i]%2][1][0]==1&&dp2[rr][(convback[i]+1)%2][1][0]==1)||
				(dp2[rr][convback[i]%2][0][0]==1&&dp2[rr][(convback[i]+1)%2][0][0]==1)){
					allrows =1;
				}
			}
			else{
				if(findx(i)==1)
					dp2[rr][convback[i]%2][0][1] = 1;
				else
					dp2[rr][convback[i]%2][1][1] = 1;
				if((dp2[rr][convback[i]%2][0][1]==1&&dp2[rr][convback[i]%2][1][1]==1)||
				(dp2[rr][convback[i]%2][1][1]==1&&dp2[rr][(convback[i]+1)%2][1][1]==1)||
				(dp2[rr][convback[i]%2][0][1]==1&&dp2[rr][(convback[i]+1)%2][0][1]==1)){
					allculms =1;
				}
			}
		}
		if(allrows&&allculms){
			cout<<0;
			break;
		}
		if(allrows){
			cout<<powmod(2,n-r,mod);
			break;
		}
		if(allculms){
			cout<<powmod(2,m-l,mod);
			break;
		}
		cout<<(powmod(2,n-r,mod)+powmod(2,m-l,mod)-1-(k==0)+mod)%mod;
	}
}

Compilation message (stderr)

plusminus.cpp: In function 'int main()':
plusminus.cpp:118:83: warning: unused variable 'lll' [-Wunused-variable]
  118 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 1, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                                                                   ^~~
plusminus.cpp:118:92: warning: unused variable 'rrr' [-Wunused-variable]
  118 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 1, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                                                                            ^~~
plusminus.cpp:118:101: warning: unused variable 'inf' [-Wunused-variable]
  118 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 1, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                                                                                     ^~~
plusminus.cpp:122:15: warning: unused variable 'dec' [-Wunused-variable]
  122 |   long double dec = 0;
      |               ^~~

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