QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#593966#8236. Snake MoveabsabsWA 585ms223220kbC++235.4kb2024-09-27 17:36:422024-09-27 17:36:42

Judging History

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

  • [2024-09-27 17:36:42]
  • 评测
  • 测评结果:WA
  • 用时:585ms
  • 内存:223220kb
  • [2024-09-27 17:36:42]
  • 提交

answer

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(x) cout << #x << "=" << x << endl
// using i128 = __int128_t;
#define int unsigned long long
typedef pair<int, int> PII;
typedef long long ll;
inline void read(int &x)
{
    char ch = getchar();
    int f = 1;
    x = 0;
    while (!isdigit(ch) && ch ^ '-')
        ch = getchar();
    if (ch == '-')
        f = -1, ch = getchar();
    while (isdigit(ch))
        x = x * 10 + ch - '0', ch = getchar();
    x *= f;
}
void write(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
    return;
}
// int a[N];
const int N = 5e5 + 10;
const int mod = 1e9 + 7;
#define pre(i,a,b) for(int i=a;i<=b;i++)
int qmi(int a,int b)
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
struct node 
{
    int a,b,c;
}a[N];
ll ans[N];
ll n,m,k;
ll tim[3010][3010];
char v[3010][3010];
ll dist[3010][3010];
ll dx[]={1,-1,0,0};
ll dy[]={0,0,1,-1};
ll vis[3010][3010];
ll st[3010][3010];
queue<PII>q;
void rCL()
{
    cin>>n>>m>>k;
    int a,b,aa,bb;
    // cout<<n<<endl;
    // return;
    vector<PII>poi;
    for(int i=1;i<=k;i++){
        cin>>a>>b;
        poi.push_back({a,b});
        if(i==1){
            aa=a;
            bb=b;
        }
        if(i==1)continue;
        if(i!=k)tim[a][b]=k-i+1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>v[i][j];
        }
    }
    
    vis[aa][bb]=1;
    q.push({aa,bb});
    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        // cout<<xx<<" "<<yy<<endl;
        for(int i=0;i<4;i++){
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(xx<1||xx>n||yy<1|yy>m||v[xx][yy]=='#'||vis[xx][yy])continue;
            if(dist[xx][yy]+1<tim[xx][yy])continue;
            q.push({xx,yy});
            vis[xx][yy]=1;
            dist[xx][yy]=dist[x][y]+1;
        }
    }
    //////////////////
    // q.push({aa,bb});
    // for(int i=1;i<4;i++)
    // {
    //     int xx=aa+dx[i];
    //     int yy=bb+dy[i];
    //     if(xx<1||xx>n||yy<1|yy>m||v[xx][yy]=='#'||dist[xx][yy] != 0)continue;
    //     q.push({xx,yy});
    // }
    // for(auto [a,b]:poi){
    //     q.push({a,b});
    // }
    // while(!q.empty())
    // {
    //     int x=q.front().first;
    //     int y=q.front().second;
    //     q.pop();
    //     // cout << x << " tttt " << y << endl;
    //     // cout<<xx<<" "<<yy<<endl;
    //     for(int i=0;i<4;i++){
    //         int xx=x+dx[i];
    //         int yy=y+dy[i];
    //         if(xx<1||xx>n||yy<1|yy>m||v[xx][yy]=='#'||dist[xx][yy]==0)continue;
    //         if(dist[xx][yy]+1<tim[x][y])continue;
    //         // q.push({xx,yy});
    //         // st[xx][yy]=1;
    //         // dist[xx][yy]=min(dist[xx][yy],dist[x][y]+1);
    //         if(dist[x][y])dist[x][y]=min(dist[xx][yy]+1,dist[x][y]);
    //         else dist[x][y]=dist[xx][yy]+1;
    //     }
    // }
    ////////////////
    poi.pop_back();
    for(int i=0;i<poi.size();i++){
        if(i==0)continue;
        int a=poi[i].first;
        int b=poi[i].second;
        dist[a][b]=k+i-2;
        q.push({a,b});
    }

    /////
    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        // cout<<xx<<" "<<yy<<endl;
        for(int i=0;i<4;i++){
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(xx<1||xx>n||yy<1|yy>m||v[xx][yy]=='#'||st[xx][yy])continue;
            // if(dist[xx][yy]+1<tim[xx][yy])continue;
            q.push({xx,yy});
            st[xx][yy]=1;
            dist[xx][yy]=min(dist[xx][yy],dist[x][y]+1);
        }
    }


    ///
    reverse(poi.begin(),poi.end());
    if(poi.size() > 2)poi.pop_back();
    for(auto [a,b]:poi){
        // cout<<endl;
        // cout<<a<<" "<<b<<endl;
        for(int i=0;i<4;i++){
            int xx=a+dx[i];
            int yy=b+dy[i];
            if(xx<1||xx>n||yy<1|yy>m||v[xx][yy]=='#')continue;
            // cout<<xx<<" "<<yy<<endl;
            // cout<<dist[xx][yy]+1<<" "<<tim[a][b]<<endl<<endl;;
            if(dist[xx][yy]+1<tim[a][b])continue;
            dist[a][b]=min(dist[xx][yy]+1,dist[a][b]);
            
        }

    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            // cout<<dist[i][j]<<" ";
            if(i==aa&&j==bb){
                continue;
            }
            int qwq=max(dist[i][j],(tim[i][j]));
            qwq=dist[i][j];
            ans+=qwq*qwq;
            // cout<<qwq*qwq<<endl;
        }
        // cout<<endl;
    }
    // cout<<endl;
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++){
    //         cout<<tim[i][j]<<" ";
    //         if(i==aa&&j==bb){
    //             continue;
    //         }
    //         int qwq=max(dist[i][j],(tim[i][j]+1));
    //         ans+=qwq*qwq;
    //         // cout<<qwq*qwq<<endl;
    //     }
    //     cout<<endl;
    // }
    cout<<ans<<endl;

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 11836kb

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: 0ms
memory: 11844kb

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

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 315ms
memory: 156468kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 375ms
memory: 152384kb

input:

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

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 64ms
memory: 18072kb

input:

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

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 62ms
memory: 19924kb

input:

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

output:

1

result:

ok single line: '1'

Test #8:

score: -100
Wrong Answer
time: 585ms
memory: 223220kb

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:

49803413398430

result:

wrong answer 1st lines differ - expected: '49803365625286', found: '49803413398430'