//https://oj.uz/problem/view/BOI13_tracks
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
// typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>ordered_set;//for just using as a set
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>ordered_set;//for using multiset
//find by order=value at that index
//orderof key= gives index of that number // if number 7 not in the set but it will show the index number if it was there in sorted array.
//remember index is 0 based & if a number is already there then it will give the lowerbound
#define MAX 1e6+1
class disjointSet{
vector<int> rank,parent,size;
public:
disjointSet(int n){
rank.resize(n+1,0);//for both 0based and 1 based indexing
parent.resize(n+1);
size.resize(n+1);
for(int i=0;i<=n;i++){
parent[i]=i;
size[i]=1;
}
}
int findupar(int node){//finds the ultimate parent//O(4alpha)==constant
if(node==parent[node]){
return node;
}
else{
return parent[node]=findupar(parent[node]);
}
}
void unionbyrank(int u,int v){//O(4alpha)==constant
int ulpu=findupar(u);
int ulpv=findupar(v);
if(ulpv==ulpu){
return;
}
if(rank[ulpu]<rank[ulpv]){
parent[ulpu]=parent[ulpv];
}
else if(rank[ulpu]>rank[ulpv]){
parent[ulpv]=parent[ulpu];
}
else{
parent[ulpv]=parent[ulpu];
rank[ulpu]++;
}
}
void unionbysize(int u,int v){//O(4alpha)==constant
int ulpu=findupar(u);
int ulpv=findupar(v);
if(ulpv==ulpu){
return;
}
if(size[ulpu]<size[ulpv]){
parent[ulpu]=ulpv;
size[ulpv]+=size[ulpu];
}
else{
parent[ulpv]=ulpu;
size[ulpu]+=size[ulpv];
}
}
};
bool cmp(const pair<int, int>& a,const pair<int, int>& b){
if (a.first != b.first)
return (a.first < b.first);
else
return (a.second > b.second);
}
struct cmp1{//for use in set of pairs
bool operator()(const pair<int, int>& a, const pair<int, int>& b) const {
if (a.first != b.first)
return a.first > b.first; // Sort by first element in descending order
return a.second < b.second; // Sort by second element in ascending order
}
};
int mod_power(int x,int y,int m){//for calculating inverse through this check that m is prime x is indivisible by m and then a^(m-2)mod m=(a^-1)mod m
int res=1;//put y=m-2 to get inverse mod
while(y>0){
if(y%2==1){
res=(res*1LL*x)%m;
y--;
}
else{
x=(x*1LL*x)%m;
y/=2;
}
}
return res;
}
int bin_exp(int x,int y){//for calculating inverse through this check that m is prime x is indivisible by m and then a^(m-2)mod m=(a^-1)mod m
int res=1;//put y=m-2 to get inverse mod
while(y>0){
if(y%2==1){
res=(res*1LL*x);
y--;
}
else{
x=(x*1LL*x);
y/=2;
}
}
return res;
}
vector<int> prime;
void SieveOfEratosthenes(){
prime.assign(MAX,0);
for(int i=2;i<MAX;i++){
prime[i]=1;
}
for (int p = 2; p * p <= MAX; p++) {
if (prime[p] == true) {
for (int i = p * p; i <= MAX; i += p)
prime[i] = false;
}
}
}
vector<int> smp;
void spf(){
smp.assign(MAX,0);
smp[0]=1;
for(int i=1;i<MAX;i++){
smp[i]=i;
}
for(int i=2;i*i<MAX;i++){
if(smp[i]==i){
for(int k=i*i;k<MAX;k=k+i){
if(smp[k]==k){
smp[k]=i;
}
}
}
}
}
vector<int> dj(vector<vector<pair<int,int>>> &adj,int n,int src){
vector<int> dist(n);
int ans=0;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
for(int i=0;i<n;i++) dist[i]=1e18;//length of dist array is equal to number of nodes in graph
dist[src]=0;
pq.push({0,src});
while(!pq.empty()){
int dis=pq.top().first;
int node=pq.top().second;
pq.pop();
if(dis!=dist[node]){
continue;
}
for(auto it:adj[node]){
int edgeweight=it.second;
int adjnode=it.first;
if(dis+edgeweight<dist[adjnode]){
dist[adjnode]=dis+edgeweight;
pq.push({dist[adjnode],adjnode});
}
}
}
return dist;
}
vector<int> bfs(vector<vector<int>> &adj,int n,int src){
vector<int> dist(n,1e18);
dist[src]=0;
queue<int> q;
vector<int> vis(n);
vis[src]=1;
q.push(src);
while(!q.empty()){
int a=q.front();q.pop();
for(auto i:adj[a]){
if(vis[i]==0){
q.push(i);
dist[i]=dist[a]+1;
vis[i]=1;
}
}
}
return dist;
}
int phi(int n) {
int result = n;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
while (n % i == 0)
n /= i;
result -= result / i;
}
}
if (n > 1)
result -= result / n;
return result;
}
int count_relprime_till_l(int n,int l){//counts the number of relative prime numbers of n under l;
vector<int> prime;
for(int i=2;i*i<=n;i++){
if(n%i==0){
prime.push_back(i);
while(n%i==0){
n/=i;
}
}
}
if(n>1){
prime.push_back(n);
}
//prime vector contains prime factorization of n
pair<int,int> p={0,0};
int len=prime.size();
for(int i=1;i<(1<<len);i++){// did this for subset making if(n==3) i= 001,010,011,100 and so on
int mult=1;
for(int j=0;j<len;j++){
if(i&(1<<j)){
mult*=prime[j];
}
}
if(__builtin_popcount(i)%2==1){// built in function counts the number of set bits
p.second+=l/mult;
}
else{
p.first+=l/mult;
}
}
return l-(p.second-p.first);//rel prime= l-(not rel prime)
}
struct Hashing {
vector<vector<int>> hs;
vector<int> PWX, PWY;
int n, m;
static const int PX = 3731, PY = 2999, mod = 998244353;
Hashing() {}
Hashing(vector<string>& s) {
n = (int)s.size(), m = (int)s[0].size();
hs.assign(n + 1, vector<int>(m + 1, 0));
PWX.assign(n + 1, 1);
PWY.assign(m + 1, 1);
for (int i = 0; i < n; i++) PWX[i + 1] = 1LL * PWX[i] * PX % mod;
for (int i = 0; i < m; i++) PWY[i + 1] = 1LL * PWY[i] * PY % mod;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
hs[i + 1][j + 1] = s[i][j] - 'a' + 1;
}
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j < m; j++) {
hs[i][j + 1] = (hs[i][j + 1] + 1LL * hs[i][j] * PY % mod) % mod;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j <= m; j++) {
hs[i + 1][j] = (hs[i + 1][j] + 1LL * hs[i][j] * PX % mod) % mod;
}
}
}
int get_hash(int x1, int y1, int x2, int y2) { // 1-indexed
assert(1 <= x1 && x1 <= x2 && x2 <= n);
assert(1 <= y1 && y1 <= y2 && y2 <= m);
x1--;
y1--;
int dx = x2 - x1, dy = y2 - y1;
return (1LL * (hs[x2][y2] - 1LL * hs[x2][y1] * PWY[dy] % mod + mod) % mod -
1LL * (hs[x1][y2] - 1LL * hs[x1][y1] * PWY[dy] % mod + mod) % mod * PWX[dx] % mod + mod) % mod;
}
int get_hash() {
return get_hash(1, 1, n, m);
}
};
#define mod 1000000007
int LEN=5e5+5;
vector<int> fac,inv;
int ncr(int n,int r){
if(n<r){
return 0;
}
int res=fac[n];
res*=inv[n-r];res%=mod;
res*=inv[r];res%=mod;
return res;
}
void fac_in(){
fac.assign(LEN,1);
inv.assign(LEN,1);
inv[0]=mod_power(1,mod-2,mod);
for(int i=1;i<LEN;i++){
fac[i]=fac[i-1]*i;fac[i]%=mod;
inv[i]=mod_power(fac[i],mod-2,mod);
}
}
vector<int> po;
void power(int x){
int len=2e5+5;
po.assign(len,1);
for(int i=1;i<len;i++){
po[i]=po[i-1]*x;po[i]%=mod;
}
}
vector<string> v;
vector<vector<int>> vec;
vector<int> dx={-1,0,1,0};
vector<int> dy={0,-1,0,1};
int h,w;
vector<vector<int>> adj;
void f(int x,int y,int in){
// cout<<x<<" "<<y<<" "<<in<<endl;
for(int i=0;i<4;i++){
if(x+dx[i]>=0&&x+dx[i]<h&&y+dy[i]>=0&&y+dy[i]<w&&vec[x+dx[i]][y+dy[i]]==-1&&v[x+dx[i]][y+dy[i]]==v[x][y]){
vec[x+dx[i]][y+dy[i]]=in;
f(x+dx[i],y+dy[i],in);
}
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>h>>w;
v.assign(h,"");
for(int i=0;i<h;i++){
cin>>v[i];
}
// for(auto &i:v){
// cout<<i<<"\n";
// }
vec.assign(h,vector<int>(w,-1));
int k=0;
set<int> r,fox;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(vec[i][j]==-1){
if(v[i][j]=='R'){
r.insert(k);
vec[i][j]=k;
f(i,j,k);
k++;
}
else if(v[i][j]=='F'){
fox.insert(k);
vec[i][j]=k;
f(i,j,k);
k++;
}
}
}
}
// for(auto &i:vec){
// for(auto &i:i){
// cout<<i<<" ";
// }
// cout<<"\n";
// }
// cout<<"YES"<<endl;
map<int,set<int>> m;
disjointSet ds(r.size());
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(v[i][j]=='F'){
for(int p=0;p<4;p++){
if(i+dx[p]>=0&&i+dx[p]<h&&j+dy[p]>=0&&j+dy[p]<w&&vec[i+dx[p]][j+dy[p]]!=-1&&v[i+dx[p]][j+dy[p]]!=v[i][j]){
m[vec[i][j]].insert(vec[i+dx[p]][j+dy[p]]);
}
}
}
}
}
for(auto &i:m){
if(i.second.size()>1){
auto it=*i.second.begin();
for(auto &i:i.second){
ds.unionbysize(it,i);
}
}
}
set<int> cnt;
for(auto &i:r){
cnt.insert(ds.findupar(i));
}
int ans=cnt.size();
m.clear();
cnt.clear();
disjointSet ds1(fox.size());
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(v[i][j]=='R'){
for(int p=0;p<4;p++){
if(i+dx[p]>=0&&i+dx[p]<h&&j+dy[p]>=0&&j+dy[p]<w&&vec[i+dx[p]][j+dy[p]]!=-1&&v[i+dx[p]][j+dy[p]]!=v[i][j]){
m[vec[i][j]].insert(vec[i+dx[p]][j+dy[p]]);
}
}
}
}
}
for(auto &i:m){
if(i.second.size()>1){
auto it=*i.second.begin();
for(auto &i:i.second){
ds1.unionbysize(it,i);
}
}
}
for(auto &i:fox){
cnt.insert(ds1.findupar(i));
}
ans+=cnt.size();
cout<<ans<<"\n";
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
