oj.uz

Submission #1081212

# Submission time Handle Problem Language Result Execution time Memory
1081212 2024-08-29T19:45:31 Z vasu_boda_ Tracks in the Snow (BOI13_tracks) C++17
0 / 100
 1207 ms 1048576 KB 
/*<------------------------------------------------------------------------------------										      	
---------------------------------------------------------------------------------------
----------------------MADE--BY--VB-----------------------------------------------------
---------------------------------------------------------------------------------------
------------------------------------------------------------------------------------>*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// ifstream  i_data("mixmilk.in");
// ofstream  o_data("mixmilk.out");

// #define cin  i_data
// #define cout o_data

/*<--------------------------------DATA--STRUCTURES----------------------------------->*/
#define ll long long
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define vi vector<int>
#define vll vector<long long>
#define mii map<int, int>
#define mll map<long long, long long>
#define si set<int>
#define sc set<char>
#define moj_karvani  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
// only less behave as set
//less_equal as multiset
//we can replace less with greater for descending order
/*<--------------------------------FUNCTIONS------------------------------------------->*/
string itob(int num) {if (num == 0) return "0";string binaryString;while (num > 0) {binaryString = (num % 2 == 0 ? "0" : "1") + binaryString;num /= 2;}return binaryString;}
int btoi(const string& binaryString) {return stoi(binaryString, nullptr, 2);}
void print_binary(int num){for(int i=10;i>=0;i--){cout<<((num>>i) & 1);}cout<<endl;}
string to_upper(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A'; return a; }
string to_lower(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A'; return a; }
bool comp(const pair<int, int>& a, const pair<int, int>& b) {if (a.first == b.first) {return a.second < b.second; }return a.first <b.first; };
vector<int> find_intersection(int a,int b,int c,int d,int p,int q,int r ,int s){vector<int>v;int l=max(a,p);int m=max(b,q);int n=min(c,r);int o=min(d,s);int x=n-l;int y=o-m;if(x<0 || y<0){return v;}v.push_back(l);v.push_back(m);v.push_back(n);v.push_back(o);return v;}
/*<-----------------------------BASIC--MATH----------------------------------------->*/
const ll M=1e9+7,N=1e5+5;
ll gcd(ll a,ll b) { if (b==0) return a; return gcd(b, a%b); }
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
//ll power(ll a,ll b){if(b==0) return 1;ll res=power(a,b/2);if(b&1){return a*res*res;}else{return res*res;}}
ll power(ll a, ll b){ll ans=1;while(b){if(b&1){ans=ans*a;}a=a*a;b>>=1;}return ans;}
//ll isPrime(ll a){ if (a != 2 && a % 2 == 0 || a < 2) return 0;  for(ll i = 3; i * i <= a; i += 2) if(a % i == 0) return 0; return 1;}
bool isPrime(int number){if (number <= 1)return false;if (number == 2)return true;if (number % 2 == 0) return false;int boundary = (int)floor(sqrt(number));for (int i = 3; i <= boundary; i += 2)if (number % i == 0)return false;return true;}
/*
SIEVE
int is_prime[1000001];
void seive(){
	int maxN=1000000;
	is_prime[0]=is_prime[1]=0;
	for(int i=2;i<=maxN;i++){
		is_prime[i]=1;
	}
	for(int i=1;i*i<=maxN;i++){
		if(is_prime[i]){
			for(int j=i*i;j<=maxN;j+=i){
				is_prime[j]=0;
			}
		}
	}
}
*/
/*<---------------------------------Solve--here-------------------------------------------->*/

vector<vector<char>>g(4000,vector<char>(4000,'.'));
vector<vector<int>>vis(4000,vector<int>(4000,0));
set<char>s;
void dfs(int i,int j,int m,int n){
    if(i<0 || j<0 || i>=m || j>=n){
        return;
    }
    if(vis[i][j] || g[i][j]=='.')return;
    s.insert(g[i][j]);
    vis[i][j]=1;
    dfs(i-1,j,m,n);
    dfs(i+1,j,m,n);
    dfs(i,j-1,m,n);
    dfs(i,j+1,m,n);
}
void solve(){
	int m,n;
    cin>>m>>n;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            cin>>g[i][j];
        }
    }
    int ans=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(!vis[i][j] && g[i][j]!='.'){
                s.clear();
                dfs(i,j,m,n);
                ans+=s.size();
            }
        }
    }
    cout<<ans<<endl;
}

/*<-------------------------------Main--Function------------------------------------------>*/
int main(){
	moj_karvani;
	int t=1;
	//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

/*<-------------------------------Thank--You----------------------------------------------->*/

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 100436 KB Output isn't correct
2 Incorrect 46 ms 78932 KB Output isn't correct
3 Incorrect 41 ms 78932 KB Output isn't correct
4 Incorrect 53 ms 95828 KB Output isn't correct
5 Incorrect 42 ms 79700 KB Output isn't correct
6 Incorrect 38 ms 78840 KB Output isn't correct
7 Incorrect 36 ms 78932 KB Output isn't correct
8 Incorrect 38 ms 79444 KB Output isn't correct
9 Incorrect 43 ms 79048 KB Output isn't correct
10 Incorrect 42 ms 79696 KB Output isn't correct
11 Incorrect 43 ms 83372 KB Output isn't correct
12 Incorrect 43 ms 85764 KB Output isn't correct
13 Incorrect 45 ms 79700 KB Output isn't correct
14 Incorrect 42 ms 79696 KB Output isn't correct
15 Incorrect 53 ms 83028 KB Output isn't correct
16 Incorrect 62 ms 100432 KB Output isn't correct
17 Incorrect 44 ms 83792 KB Output isn't correct
18 Incorrect 51 ms 95796 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 80292 KB Output isn't correct
2 Incorrect 87 ms 94240 KB Output isn't correct
3 Incorrect 345 ms 210256 KB Output isn't correct
4 Incorrect 113 ms 102328 KB Output isn't correct
5 Incorrect 396 ms 334488 KB Output isn't correct
6 Runtime error 785 ms 1048576 KB Execution killed with signal 9
7 Incorrect 44 ms 79700 KB Output isn't correct
8 Incorrect 42 ms 80208 KB Output isn't correct
9 Incorrect 36 ms 80212 KB Output isn't correct
10 Incorrect 35 ms 78932 KB Output isn't correct
11 Incorrect 35 ms 79440 KB Output isn't correct
12 Incorrect 35 ms 80208 KB Output isn't correct
13 Incorrect 72 ms 94388 KB Output isn't correct
14 Incorrect 59 ms 87892 KB Output isn't correct
15 Incorrect 75 ms 110932 KB Output isn't correct
16 Incorrect 57 ms 87120 KB Output isn't correct
17 Incorrect 133 ms 113524 KB Output isn't correct
18 Incorrect 236 ms 203604 KB Output isn't correct
19 Incorrect 120 ms 102224 KB Output isn't correct
20 Incorrect 105 ms 108880 KB Output isn't correct
21 Incorrect 221 ms 151380 KB Output isn't correct
22 Incorrect 383 ms 334676 KB Output isn't correct
23 Incorrect 231 ms 151948 KB Output isn't correct
24 Incorrect 313 ms 252192 KB Output isn't correct
25 Incorrect 706 ms 593588 KB Output isn't correct
26 Runtime error 752 ms 1048576 KB Execution killed with signal 9
27 Runtime error 776 ms 1048576 KB Execution killed with signal 9
28 Runtime error 832 ms 1048576 KB Execution killed with signal 9
29 Runtime error 793 ms 1048576 KB Execution killed with signal 9
30 Runtime error 774 ms 1048576 KB Execution killed with signal 9
31 Runtime error 760 ms 1048576 KB Execution killed with signal 9
32 Incorrect 1207 ms 984660 KB Output isn't correct