QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#711551#8236. Snake MovesillkWA 1ms7968kbC++112.8kb2024-11-05 12:00:362024-11-05 12:00:51

Judging History

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

  • [2024-11-05 12:00:51]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7968kb
  • [2024-11-05 12:00:36]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int __int128
#define PII pair<int,int>

const int N=3010,inf=1e15;
int n,m,k,a[N][N],change[4][2]={{1,0},{-1,0},{0,1},{0,-1}},mark[N][N],dis[N][N];


inline __int128 read()//__int128,可以实现加减乘除的运算,大部分OJ平台都能用,必须用快读
{
  __int128 x = 0, f = 1;
  char ch = getchar();
  while(ch < '0' || ch > '9')
	{
    if(ch == '-')
    	f = -1;
    ch = getchar();
  }
  while(ch >= '0' && ch <= '9')
	{
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}

inline void print(__int128 x)
{
  if(x < 0)
	{
    putchar('-');
    x = -x;
  }
  if(x > 9)
    print(x / 10);
  putchar(x % 10 + '0');
}

struct edge
{
	int posx,posy,level;
	bool operator < (edge x) const 
	{
		if(level==x.level)
		{
			return posx==x.posx?posy>x.posy:posx>x.posx;
		}
		return level>x.level;
	}
};

void solve()
{
	int n=read(),m=read(),k=read();
	map<PII,int> mp;
	vector<PII> snake;
	int x,y;
	for(int i=1;i<=k;i++)
	{
		int x=read(),y=read();
		snake.push_back({x,y});
		mp[{x,y}]=k-i+1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			dis[i][j]=inf;
		}
	}
	string tmp;
	for(int i=1;i<=n;i++)
	{
		cin>>tmp;
		for(int j=1;j<=m;j++)
		{
			a[i][j]=tmp[j-1];
			if(a[i][j]=='#')
			{
				mark[i][j]=1;
				dis[i][j]=0;
			}
		}
	}
	// for(auto i=mp.begin();i!=mp.end();i++)
	// {
	// 	cout<<i->first.first<<" "<<i->first.second<<" "<<i->second<<endl;
	// }
	// cout<<endl;
	priority_queue<edge> q;
	q.push({snake[0].first,snake[0].second,0});
	int pnow=0;
	mp.erase(snake[k-1-pnow]);
	while(!q.empty())
	{
		auto now=q.top();
		q.pop();
		int nx=now.posx,ny=now.posy,nl=now.level;
		// cout<<nx<<" "<<ny<<" "<<nl<<endl;
		if(mark[nx][ny])
		{
			continue;
		}
		if(nl!=pnow)
		{
			pnow=nl;
			mp.erase(snake[k-1-pnow]);
		}
		mark[nx][ny]=1;
		dis[nx][ny]=nl;
		for(int i=0;i<4;i++)
		{
			int tx=nx+change[i][0],ty=ny+change[i][1];
			if(tx<=0||tx>n||ty<=0||ty>m||mark[tx][ty]||dis[tx][ty]<=dis[nx][ny]+1)
			{
				continue;
			}
			if(mp.count({tx,ty})&&mp[{tx,ty}]>dis[nx][ny]+1)
			{
				dis[tx][ty]=mp[{tx,ty}];
				q.push({tx,ty,dis[tx][ty]});
			}
			else
			{
				dis[tx][ty]=dis[nx][ny]+1;
				q.push({tx,ty,dis[tx][ty]});
			}
		}
	}
	int tot=0,mod=1;
	for(int i=1;i<=64;i++)
	{
		mod=mod*2;
	}
	// print(mod);
	// cout<<endl;
	// cout<<mod<<endl;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			// cout<<dis[i][j]<<" ";
			if(dis[i][j]!=inf)
			{
				tot+=dis[i][j]%mod*dis[i][j]%mod;
				tot%=mod;
			}
		}
		// cout<<endl;
	}
	print(tot);
	// cout<<endl;
}

signed main()
{
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int t;
	// cin>>t;
	t=1;
	while(t--)
	{
		solve();
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5712kb

input:

4 5 5
3 5
3 4
3 3
3 2
4 2
.....
.....
.....
.....

output:

293

result:

ok single line: '293'

Test #2:

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

input:

2 2 4
1 1
1 2
2 2
2 1
..
..

output:

14

result:

ok single line: '14'

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 7968kb

input:

5 5 3
1 2
1 1
2 1
.....
.###.
.#.#.
.###.
.....

output:

368

result:

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