QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#61020 | #3892. Efficiently Elevated | SayedHassan# | WA | 176ms | 32332kb | C++ | 1.7kb | 2022-11-09 05:56:00 | 2022-11-09 05:56:03 |
Judging History
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'