QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#416431#8236. Snake MoveGodwang#WA 600ms94408kbC++143.5kb2024-05-21 20:35:332024-05-21 20:35:36

Judging History

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

  • [2024-05-21 20:35:36]
  • 评测
  • 测评结果:WA
  • 用时:600ms
  • 内存:94408kb
  • [2024-05-21 20:35:33]
  • 提交

answer

#include <iostream>
using namespace std;
#include <set>
#include <algorithm>
#include <cmath>
#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <string.h>
#include <stdlib.h>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <stack>
#include <queue>
#include <ctype.h>
#include <vector>
#include <random>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define pii pair<int, int>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define pll pair<ll ,ll > 
#define endl '\n'
const double pai = acos(-1);
ll extend_gcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll d = extend_gcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
ll fastpow(ll a, ll n, ll mod)
{
    ll ans = 1;
    a %= mod;
    while (n)
    {
        if (n & 1)
            ans = (ans * a)%mod; //% mod
        a = (a * a)%mod;         //% mod
        n >>= 1;
    }
    return ans;
}
int dir[4][2] =
    {
        {0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // d a w s

const int inf = 1000000000;
const ll mod = 1e9 + 7, P1 = 13331;
const double eps = 1e-7;
const int N =3000  + 10, M = 1e6 + 10;

int n,m,k;
bool vis[N][N];
ull ans[N][N];
string ss[N];

int a[N][N];

struct node
{
    int x,y,t,s;
    node(int a,int b,int c,int d)
    {
        x=a;
        y=b;
        t=c;
        s=d;
    }
    bool operator <(const node &b) const
    {
        return t>b.t;
    }
    // bool operator > (const node &b)const{
    //     return t>b.t;
    // }
};

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  //  freopen("ain.txt", "r", stdin);freopen("aout.txt", "w", stdout);
    cin>>n>>m>>k;
    int xx,yy;
    rep(i,1,k)
    {
        int x,y;
        cin>>x>>y;
        if(i==1)
        {
            xx=x;
            yy=y;
        }
        a[x][y]=k-i+1;
    }
    rep(i,1,n)
    {
        cin>>ss[i];
        ss[i]=' '+ss[i];
    }
    rep(i,1,n)
    {
        rep(j,1,m)
        {
            ans[i][j]=inf;
        }
    }
    priority_queue<node> q;
    q.push(node(xx,yy,0,0));
    vis[xx][yy]=1;
    while(q.size())
    {
        //
        //cout<<111111;
        node u=q.top();
        q.pop();
        int x=u.x,y=u.y,t=u.t,s=u.s;
        ans[x][y]=min(ans[x][y],(ull)t);
       // cout<<"vis: "<<x<<' '<<y<<endl;
        
        rep(i,0,3)
        {
            int xx=x+dir[i][0],yy=y+dir[i][1];
            if(xx<1||xx>n||yy<1||yy>m||vis[xx][yy]||ss[xx][yy]=='#')
            {
                continue;
            }
            if(t+s+1>=a[xx][yy])//buhui
            {
                q.push(node(xx,yy,t+1,s));
                vis[xx][yy]=1;
                //
               // cout<<11111;
            }
            else
            {
                int temp=a[xx][yy]-(t+1+s);
                q.push(node(x,y,t+ temp  , s+temp ));
               // cout<<2222222;
            }

        }
    }
    ull anss=0;
    rep(i,1,n)
    {
        rep(j,1,m)
        {
            if(ans[i][j]==inf)
            {
                continue;
            }
            ull temp=ans[i][j]*ans[i][j];
            //
            //cout<<ans[i][j]<<" ";
            //
            anss+=temp;
        }
        //
       // cout<<endl;
        //
    }
    cout<<anss;
    return 0;
}

详细

Test #1:

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

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: 7652kb

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: 1ms
memory: 7948kb

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 591ms
memory: 94224kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 590ms
memory: 92484kb

input:

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

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 24ms
memory: 86784kb

input:

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

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 24ms
memory: 85964kb

input:

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

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 600ms
memory: 91208kb

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:

49803365625286

result:

ok single line: '49803365625286'

Test #9:

score: -100
Wrong Answer
time: 599ms
memory: 94408kb

input:

3000 3000 10
2015 1932
2015 1931
2015 1930
2015 1929
2016 1929
2017 1929
2018 1929
2018 1928
2018 1927
2017 1927
#...#...#..#.........#.......#####....#...###..#..###..###....##.....#..#..#...#.....##...##.#..#..##.###.........##.....#....#..##.##.#.#.##.#.#.#.....#....##.##.#..##....#....#...#.#......

output:

22509095749225

result:

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