QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#61020#3892. Efficiently ElevatedSayedHassan#WA 176ms32332kbC++1.7kb2022-11-09 05:56:002022-11-09 05:56:03

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-09 05:56:03]
  • 评测
  • 测评结果:WA
  • 用时:176ms
  • 内存:32332kb
  • [2022-11-09 05:56:00]
  • 提交

answer


#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define sc second

/*const int N=1e5+5;
int n,m;
int c[N],a[N],b[N],p[N];*/
int di[]= {1,0,-1,0};
int dj[]= {0,1,0,-1};
const int N=505;
map<int,vector<pair<int,int> > >mp;
map<pair<int,int>,vector<pair<int,int>>> adj;
int h,w;
int a[N][N],vis[N][N],ch=0;
bool valid(int x,int y)
{
	if(x>=h||y>=w||x<0||y<0)
		return false;
	return true;
}
void dfs(int x,int y,int par)
{
	if(vis[x][y])
	{
		if(a[x][y]>par)
			ch=1;
		return;
	}
	vis[x][y]=1;
	for(auto node:adj[ {x,y}])
	{
		dfs(node.fi,node.sc,par);
	}
}
int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	/*cin>>n>>m;
	for(int i=0;i<m;i++)
	{
	    cin>>c[i]>>a[i];
	    p[c[i]]=a[i];
	}
	for(int i=0;i<n;i++)
	{
	    cin>>b[i];
	}*/
	cin>>h>>w;
	set<int> s;
	for(int i=0; i<h; i++)
	{
		for(int j=0; j<w; j++)
		{
			cin>>a[i][j];
			mp[a[i][j]].push_back({i,j});
			s.insert(a[i][j]);

		}
	}
	for(int i=0; i<h; i++)
	{
		for(int j=0; j<w; j++)
		{
			for(int k=0; k<4; k++)
			{
				int x=di[k]+i,y=dj[k]+j;
				if(valid(x,y)&&a[i][j]==a[x][y]||a[i][j]<a[x][y])
				{
					adj[{i,j}].push_back({x,y});
				}
			}
		}
	}
	vector<int> v;
	for(auto x:s)v.push_back(x);
	int ans=0;
	for(int i=v.size()-1;i>=0;i--)
    {
        if(v[i]==1)continue;
        for(auto x:mp[v[i]])
        {
            ch=0;
            if(!vis[x.fi][x.sc])
            {
                dfs(x.fi,x.sc,v[i]);
                ans++;
                ans-=ch;
            }
        }
    }
    cout<<ans;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3348kb

input:

3 3
1 2 3
0 0 4
7 6 5

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3316kb

input:

6 7
0 0 0 0 0 0 0
0 1 2 3 2 1 0
0 1 2 3 2 1 0
0 0 0 0 0 0 0
0 1 0 5 0 0 0
0 0 0 0 0 0 0

output:

2

result:

ok single line: '2'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3420kb

input:

4 4
1 1 2 1
2 2 1 2
1 2 2 1
2 1 2 2

output:

4

result:

ok single line: '4'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3876kb

input:

50 25
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 5 0 0 0 0 10 10 0 10 10 0 10 11 0 10 10 0 0 0 0 0 0
0 0 0 4 0 0 0 0 10 0 0 0 10 0 10 0 0 0 11 0 0 0 0 0 0
0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 4 3 0 3 4 5 0 10 0 0 0 10 0 11 0 0 0 10 0 0 0 0 0 0
0 0 0 3 0 0 0 0 10 10 0 10 1...

output:

28

result:

ok single line: '28'

Test #5:

score: 0
Accepted
time: 176ms
memory: 32332kb

input:

500 500
999999999 1000000000 999999999 1000000000 999999999 1000000000 999999999 1000000000 999999999 1000000000 999999999 1000000000 999999999 1000000000 999999999 1000000000 999999999 1000000000 999999999 1000000000 999999999 1000000000 999999999 1000000000 999999999 1000000000 999999999 100000000...

output:

125000

result:

ok single line: '125000'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3420kb

input:

15 15
0 2 0 2 0 2 0 2 0 2 0 2 0 2 0
2 0 2 0 2 0 2 0 2 0 2 0 2 0 2
0 2 0 2 0 2 0 2 0 2 0 2 0 2 0
2 0 2 0 2 0 2 0 2 0 2 0 2 0 2
0 2 0 2 0 2 0 2 0 2 0 2 0 2 0
2 0 2 0 2 0 2 0 2 0 2 0 2 0 2
0 2 0 2 0 2 0 2 0 2 0 2 0 2 0
2 0 2 0 2 0 2 0 2 0 2 0 2 0 2
0 2 0 2 0 2 0 2 0 2 0 2 0 2 0
2 0 2 0 2 0 2 0 2 0 2 0 ...

output:

112

result:

ok single line: '112'

Test #7:

score: -100
Wrong Answer
time: 4ms
memory: 5356kb

input:

500 1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

output:

1

result:

wrong answer 1st lines differ - expected: '0', found: '1'