Submission #868983

#	Time	Username	Problem	Language	Result	Execution time	Memory
868983		teesla	Golf (JOI17_golf)	C++17	0 / 100	6 ms	11096 KiB

golf

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
typedef pair<int,int> ii;
typedef pair<ii,ii> iii;

int grid[maxn][maxn];
int vis[maxn][maxn][2];

int s, t, u, v, n;

bool valid(int x, int y){

    if(x>0 and y >0 and grid[x][u] == 0) return true;
    return false;
}
int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};

int dijks(){

    vis[s][t][0] = 1;// veio na memsma col
    vis[s][t][1] = 1; // veio na mesma linha

    priority_queue<iii, vector<iii>, greater<iii>> q;
    q.push({{1,0},{s,t}});
    q.push({{1,1}, {s,t}});

    while(!q.empty()){

        auto [a,b] = q.top(); q.pop();
        auto [dist, dir] = a;
        auto [x,y] = b;

        cout << x << ' '<< y << endl;

        if(vis[x][y][dir] < dist) continue;
        if(x == u and y == v) return dist;

        for(int i=0; i<4; i++){

            int xx = x+dx[i], yy = y + dy[i];

            if(!valid(xx,yy)) continue;

            if(yy == y){

                int ddd = dist;
                if(dir == 1) ddd ++;
                if(vis[xx][yy][0] == -1 or vis[xx][yy][0] > ddd){
                    vis[xx][yy][0] = ddd;
                    q.push({{ddd, 0}, {xx,yy}});
                }
            }
            if(xx == x){

                int ddd = dist;
                if(dir = 0) ddd++;
                if(vis[xx][yy][1] == -1 or vis[xx][yy][1] > ddd){
                    vis[xx][yy][1] = ddd;
                    q.push({{ddd,1}, {xx,yy}});
                }
            }

        }
    }
    return 0;
}

int main(){

    cin >> s >> t >> u >> v >> n;

    for(int i=0; i<n; i++){

        int a,b,c,d; cin >> a >> b >> c >> d;
        a++;
        b--; c++; d--;

        for(int j = a; j<=b; j++) for(int k = c; k<=d; k++) grid[j][k] = 1;
    }

    memset(vis, sizeof(vis), -1);
    cout << dijks() << endl;
}

Compilation message (stderr)

golf.cpp: In function 'int dijks()':
golf.cpp:57:24: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   57 |                 if(dir = 0) ddd++;
      |                    ~~~~^~~
In file included from /usr/include/string.h:495,
                 from /usr/include/c++/10/cstring:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:48,
                 from golf.cpp:1:
In function 'void* memset(void*, int, size_t)',
    inlined from 'int main()' at golf.cpp:82:11:
/usr/include/x86_64-linux-gnu/bits/string_fortified.h:71:33: warning: 'void* __builtin___memset_chk(void*, int, long unsigned int, long unsigned int)' specified bound 18446744073709551615 exceeds maximum object size 9223372036854775807 [-Wstringop-overflow=]
   71 |   return __builtin___memset_chk (__dest, __ch, __len, __bos0 (__dest));
      |          ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70