oj.uz

Submission #682593

# Submission time Handle Problem Language Result Execution time Memory
682593 2023-01-16T14:52:28 Z Ammar Tracks in the Snow (BOI13_tracks) C++17
21.5625 / 100
 756 ms 310580 KB 
#include <bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<utility>
#include<set>
#include<unordered_set>
#include<list>
#include<iterator>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<bitset>
#include<random>
#include<map>
#include<unordered_map>
#include<stdio.h>
#include<complex>
#include<math.h>
#include<cstring>
#include<chrono>
#include<string>

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("no-stack-protector")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
// #pragma GCC optimize("fast-math") 

using namespace std;
#define pb push_back
#define ff first
#define ss second
#define vi vector <int>
#define vvi vector <vi>
#define pii pair<int, int>
#define ppi pair<pii, int>
#define vii vector<pii>
#define mii map<int, int>
#define mci map<char, int>
#define miv map<int, vi>
#define mis map<int, set<int>>
#define setbits(n) __builtin_popcount(n)
#define all(v) (v).begin(), (v).end()
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define endl "\n"
#define fo(i,n) for(int i=0;i<n;i++)
#define in(a,n)	for(int i=0;i<n;i++) cin>>a[i];
#define show2(a, b) cout<<a<<' '<<b<<endl
#define show3(a, b, c) cout<<a<<' '<<b<<' '<<c<<endl
#define show(arr) for (auto i:arr) cout<<i<<' '; 
#define Endl endl
const long long N=1e6+5;
const long long mod=1000000007; //998244353;
int n,m,sz;
vector<string> s;
vi dp;
int a[4005][4005],g[4005][4005];
int c[]={-1,0,0,1};
int d[]={0,-1,1,0};
bool inrange(int x, int y)
{
	return x>=0 && x<n && y>=0 && y<m;
}
void bfs(int i, int j)
{
	queue<pii> q;
	q.push(pii({i,j}));
	a[i][j]=sz;
	while(q.size())
	{
		auto p=q.front();q.pop();
		int x=p.ff,y=p.ss;
		for(int k=0;k<4;k++)
		{
			int u=x+c[k],v=y+d[k];
			if(inrange(u,v) && s[u][v]==s[i][j] && a[u][v]==-1)
			{
				q.push({u,v});a[u][v]=sz;
			}
		}
	}
	sz++;
}
void bfs2()
{
	queue<int> q;
	q.push(0);dp[0]=0;
	while(q.size())
	{
		int i=q.front();q.pop();
		// cout<<i<<endl;
		for(int j=0;j<sz;j++)
		{
			if(g[i][j] && dp[j]>1+dp[i])
			{
				dp[j]=1+dp[i];q.push(j);
			}
		}
	}
}
void cases(){
	cin>>n>>m;sz=0;
	s.clear();s.resize(n);in(s,n);
	memset(g,0,sizeof(g));
	memset(a,-1,sizeof(a));
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(s[i][j]!='.' && a[i][j]==-1)
				bfs(i,j);
		}
	}
	dp.assign(sz,N);
	
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(a[i][j]==-1)continue;
			int u=i+1,v=j+1;
			
			if(inrange(i,v) && a[i][v]!=a[i][j] && a[i][v]!=-1 )
			{
				g[a[i][v]][a[i][j]]=1;g[a[i][j]][a[i][v]]=1;
			}
			if(inrange(u,j) && a[i][j]!=a[u][j] && a[u][j]!=-1)
			{
				g[a[u][j]][a[i][j]]=1;g[a[i][j]][a[u][j]]=1;
			}
		}
	}
	// for(auto x:g)
	// {
		// show(x);cout<<endl;
	// }
	bfs2();
	int ans=0;
	for(auto x:dp)ans=max(ans,x+1);
	cout<<ans<<endl;
}

int32_t main(){
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int t=1;
    // cin>>t;
    for (int i=0; i<t; i++){
    	//cout<<"Case #"<<i+1<<": ";
		cases();
    }
    return 0;
}

Subtask #1
15.0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 170 ms 255824 KB Execution killed with signal 11
2 Correct 55 ms 125780 KB Output is correct
3 Correct 48 ms 125812 KB Output is correct
4 Correct 79 ms 126036 KB Output is correct
5 Incorrect 121 ms 125940 KB Output isn't correct
6 Correct 51 ms 125800 KB Output is correct
7 Correct 50 ms 125816 KB Output is correct
8 Correct 46 ms 125768 KB Output is correct
9 Correct 60 ms 125760 KB Output is correct
10 Incorrect 160 ms 126004 KB Output isn't correct
11 Correct 50 ms 125808 KB Output is correct
12 Runtime error 174 ms 255308 KB Execution killed with signal 11
13 Incorrect 134 ms 126024 KB Output isn't correct
14 Incorrect 120 ms 125984 KB Output isn't correct
15 Runtime error 187 ms 255772 KB Execution killed with signal 11
16 Runtime error 188 ms 255792 KB Execution killed with signal 11
17 Runtime error 171 ms 255836 KB Execution killed with signal 11
18 Correct 70 ms 126020 KB Output is correct

Subtask #2
6.5625 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 126024 KB Output isn't correct
2 Runtime error 230 ms 259936 KB Execution killed with signal 11
3 Runtime error 392 ms 302560 KB Execution killed with signal 11
4 Runtime error 255 ms 265124 KB Execution killed with signal 11
5 Runtime error 475 ms 310580 KB Execution killed with signal 11
6 Runtime error 756 ms 295328 KB Execution killed with signal 11
7 Incorrect 72 ms 125988 KB Output isn't correct
8 Incorrect 78 ms 126028 KB Output isn't correct
9 Incorrect 96 ms 125908 KB Output isn't correct
10 Correct 58 ms 125824 KB Output is correct
11 Correct 60 ms 125880 KB Output is correct
12 Runtime error 171 ms 255272 KB Execution killed with signal 11
13 Runtime error 191 ms 259920 KB Execution killed with signal 11
14 Runtime error 174 ms 257928 KB Execution killed with signal 11
15 Runtime error 240 ms 258252 KB Execution killed with signal 11
16 Runtime error 171 ms 257100 KB Execution killed with signal 11
17 Runtime error 237 ms 267924 KB Execution killed with signal 11
18 Runtime error 228 ms 268008 KB Execution killed with signal 11
19 Runtime error 225 ms 265120 KB Execution killed with signal 11
20 Runtime error 204 ms 265060 KB Execution killed with signal 11
21 Runtime error 277 ms 282452 KB Execution killed with signal 11
22 Runtime error 444 ms 310524 KB Execution killed with signal 11
23 Runtime error 323 ms 279984 KB Execution killed with signal 11
24 Runtime error 323 ms 286888 KB Execution killed with signal 11
25 Runtime error 499 ms 309112 KB Execution killed with signal 11
26 Correct 495 ms 139364 KB Output is correct
27 Runtime error 687 ms 291184 KB Execution killed with signal 11
28 Runtime error 737 ms 295308 KB Execution killed with signal 11
29 Runtime error 725 ms 293676 KB Execution killed with signal 11
30 Runtime error 744 ms 292180 KB Execution killed with signal 11
31 Runtime error 653 ms 288484 KB Execution killed with signal 11
32 Runtime error 652 ms 292140 KB Execution killed with signal 11