Submission #1200203

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200203		aryankesharwani142004	Tracks in the Snow (BOI13_tracks)	C++20	2.19 / 100	2102 ms	877108 KiB

tracks

//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;
}

• Subtask 1: 0 / 30
• Subtask 2: 2.1875 / 70