QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#687900#8236. Snake MoveasitshouldbeRE 0ms0kbC++205.5kb2024-10-29 21:48:282024-10-29 21:48:29

Judging History

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

  • [2024-10-29 21:48:29]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-10-29 21:48:28]
  • 提交

answer

#include <bits/stdc++.h>
// #pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <unordered_set>
#include <unordered_map>
//#define x first
//#define y second
#define endl '\n'
#define pi acos(-1.0)
using namespace std;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<int, PII> PIII;
typedef pair<PII, char> PIIC;
typedef long long LL;
int dx[] = {1, 0, 0, -1, -1, -1, 1, 1}, dy[] = {0, -1, 1, 0, -1, 1, -1, 1};
int mou[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int N = 3e3 + 10, M = 50 + 10, mod = 998244353, INF = 0x3f3f3f3f;
const LL inf=0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;
int n, m,k, t,body[N][N];
string g[N];
int d[N][N];
bool st[N][N];
template <typename T>
inline T read()
{
    T x = 0;
    int 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;
}
LL qmi(LL a, LL b)
{
    LL ans = 1 % mod;
    while (b)
    {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
LL inv(int x)
{
    return qmi(x, mod - 2);
}
LL Random(LL mod)
{
    LL res = INT32_MAX;
    return res * rand() * rand() % mod;
}
int sgn(double x)
{
    if (fabs(x) < eps) return 0;
    if (x < 0) return -1;
    else return 1;
}
struct Point
{
    double x, y;
    Point() {}
    Point(double _x, double _y) { x = _x;y = _y; }
    bool operator==(Point b) const { return sgn(x - b.x) == 0 && sgn(y - b.y) == 0; }
    bool operator<(Point b) const { return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x; }
    Point operator-(const Point &b) const { return Point(x - b.x, y - b.y); }
    Point operator+(const Point &b) const { return Point(x + b.x, y + b.y); }
    // 叉积
    double operator^(const Point &b) const { return x * b.y - y * b.x; }
    // 点积
    double operator*(const Point &b) const { return x * b.x + y * b.y; }
    // 数乘
    Point operator*(const double &k) const {return Point(x * k, y * k);}
    Point operator/(const double &k) const { return Point(x / k, y / k);}
};
struct Line
{
    Point s, e;
    Line() {}
    Line(Point _s, Point _e) { s = _s;e = _e; }
    // ax+by+c=0
    Line(double a, double b, double c)
    {
        if (sgn(a) == 0)
        {
            s = Point(0, -c / b);
            e = Point(1, -c / b);
        }
        else if (sgn(b) == 0)
        {
            s = Point(-c / a, 0);
            e = Point(-c / a, 1);
        }
        else
        {
            s = Point(0, -c / b);
            e = Point(1, (-c - a) / b);
        }
    }
    //`直线和线段相交判断`
    int linecrossseg(Line v)
    {
        int d1 = sgn((e - s) ^ (v.s - s));
        int d2 = sgn((e - s) ^ (v.e - s));
        if ((d1 ^ d2) == -2) return 2;     //`2 规范相交`
        return (d1 == 0 || d2 == 0);       //`1 非规范相交 0 不相交`
    }
    //`两向量平行(对应直线平行或重合)`
    bool parallel(Line v) { return sgn((e - s) ^ (v.e - v.s)) == 0; }
    //`点在线段上的判断`
    bool pointonseg(Point p) { return sgn((p - s) ^ (e - s)) == 0 && sgn((p - s) * (p - e)) <= 0; }
    //`求两直线的交点  要保证两直线不平行或重合`
    Point crosspoint(Line l)
    {
        Point u = e - s, v = l.e - l.s;
        double t = (s - l.s) ^ v / (v ^ u);
        return s + u * t;
    }
    int relation(Point p)
    {
        int c = sgn((p - s) ^ (e - s));
        if (c < 0) return 1;      //`1  在左侧`
        else if (c > 0) return 2; //`2  在右侧`
        else return 3;            //`3  在直线上`
    }
};
bool solve()
{
    priority_queue<PIII,vector<PIII>,greater<PIII>>heap;
    cin>>n>>m>>k;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++) d[i][j]=INF;
    for(int i=0;i<k;i++){
        int x,y;cin>>x>>y;
        --x,--y;
        body[x][y]=k-i;
        if(!i){
            d[x][y]=0;
            heap.push({0,{x,y}});
        }
    }
    // for(int i=0;i<n;i++,puts(""))
    //     for(int j=0;j<m;j++) cout<<body[i][j]<<" ";    
    for(int i=0;i<n;i++) cin>>g[i];
    while(heap.size()){
        auto t=heap.top();heap.pop();
        int dis=t.first,x=t.second.first,y=t.second.second;
        if(st[x][y]) continue;
        st[x][y]=1;
        for(int i=0;i<4;i++){
            int a=x+dx[i],b=y+dy[i];
            if(a<0||a>=n||b<0||b>=m||g[a][b]=='#'||st[a][b]) continue;
            if(d[a][b]>max(dis+1,body[a][b])){
                d[a][b]=max(dis+1,body[a][b]);
                heap.push({d[a][b],{a,b}});
            }
        }
    }
    // for(int i=0;i<n;i++,puts(""))
    //     for(int j=0;j<m;j++) cout<<d[i][j]<<" ";
    LL res=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(d[i][j]!=INF) res+=(LL)d[i][j]*d[i][j];
    cout<<res;
}

int main()
{
    //clock_t start,end;//定义clock_t变量
    //start = clock(); 
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0),cout.precision(10);
    // freopen("in.in","r",stdin);
    // freopen("order.in","w",stdout);
    t = 1; //cin >> t;
    while (t--) solve();
    //end = clock();   //结束时间
    //cout<<"time = "<<double(end-start)/CLOCKS_PER_SEC<<"s"<<endl;
    return 0;
}

詳細信息

Test #1:

score: 0
Runtime Error

input:

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

output:


result: