QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#323859#8236. Snake Moveucup-team987#TL 225ms49532kbC++201.3kb2024-02-10 13:50:222024-02-10 13:50:23

Judging History

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

  • [2024-02-10 13:50:23]
  • 评测
  • 测评结果:TL
  • 用时:225ms
  • 内存:49532kb
  • [2024-02-10 13:50:22]
  • 提交

answer

#include<iostream>
#include<queue>
#include<cassert>
using namespace std;
const int d[5]={0,1,0,-1};
int H,W,N;
int dist[3000][3000];
int need[3000][3000];
string S[3000];
int sx,sy;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>H>>W>>N;
	for(int i=0;i<H;i++)for(int j=0;j<W;j++)dist[i][j]=1e9;
	cin>>sx>>sy;sx--,sy--;
	for(int i=1;i<N;i++)
	{
		int x,y;cin>>x>>y;
		x--,y--;
		need[x][y]=N-i;
	}
	for(int i=0;i<H;i++)cin>>S[i];
	dist[sx][sy]=0;
	priority_queue<pair<int,int> >BODY;
	vector<int>A,B;
	A.push_back(sx*W+sy);
	for(int nd=0;;nd++)
	{
		if(A.empty()&&BODY.empty())break;
		while(!BODY.empty()&&BODY.top().first==nd)
		{
			A.push_back(BODY.top().second);
			BODY.pop();
		}
		assert(B.empty());
		for(int u:A)
		{
			int x=u/W,y=u%W;
			for(int r=0;r<4;r++)
			{
				int tx=x+d[r],ty=y+d[r+1];
				if(tx<0||ty<0||tx>=H||ty>=W||S[tx][ty]=='#'||dist[tx][ty]<=nd+1)continue;
				dist[tx][ty]=nd+1;
				if(nd+1<need[tx][ty])BODY.push(make_pair(need[tx][ty],tx*W+ty));
				else B.push_back(tx*W+ty);
			}
		}
		A.clear();
		swap(A,B);
	}
	unsigned long long ans=0;
	for(int i=0;i<H;i++)for(int j=0;j<W;j++)if(dist[i][j]<(int)1e9)
	{
		unsigned long long t=max(dist[i][j],need[i][j]);
		ans+=t*t;
	}
	cout<<ans<<endl;
}

詳細信息

Test #1:

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

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: 0
Accepted
time: 0ms
memory: 5716kb

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 127ms
memory: 48860kb

input:

3000 2900 1
1882 526
........................................................................................................#................................................................................................................................................................#................

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 225ms
memory: 47788kb

input:

2900 3000 1
1333 1773
.....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 84ms
memory: 49532kb

input:

3000 3000 1
2755 225
##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 89ms
memory: 48220kb

input:

3000 2900 1
878 738
#.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...

output:

1

result:

ok single line: '1'

Test #8:

score: -100
Time Limit Exceeded

input:

2900 3000 10
2883 1758
2883 1759
2883 1760
2883 1761
2883 1762
2884 1762
2884 1763
2883 1763
2882 1763
2882 1764
........................................................#............................#........................................................................................................

output:


result: