Submission #544634

#	Time	Username	Problem	Language	Result	Execution time	Memory
544634		pokmui9909	물통 (KOI17_bucket)	C++17	100 / 100	467 ms	18312 KiB

bucket

#include <bits/stdc++.h>
using namespace std;

int a, b, c, d;
struct water
{
    int a, b, lvl;
};
set<pair<int, int>> visited;

void push(queue<water> &q, int v1, int v2, int t)
{
    if(visited.count({v1, v2})) return;
    visited.insert({v1, v2});
    q.push({v1, v2, t});
    if(v1 == c && v2 == d)
    {
        cout << t;
        exit(0);
    }
}

void bfs()
{
    queue<water> q;
    push(q, 0, 0, 0);
    while(!q.empty())
    {
        int x=q.front().a, y=q.front().b, lvl=q.front().lvl;
        //cout << x << ' ' << y << ' ' << lvl << '\n';
        q.pop();
        push(q, a, y, lvl + 1);
        push(q, x, b, lvl + 1);
        push(q, 0, y, lvl + 1);
        push(q, x, 0, lvl + 1);
        int k;
        // 1 -> 2
        if(x >= b - y) push(q, x - b + y, b, lvl + 1);
        else push(q, 0, x + y, lvl + 1);
        // 2 -> 1
        if(y >= a - x) push(q, a, y - a + x, lvl + 1);
        else push(q, x + y, 0, lvl + 1);
    }
}

int main()
{
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);

    cin >>a >> b >> c >> d;
    bfs();
    cout << -1;
}

Compilation message (stderr)

bucket.cpp: In function 'void bfs()':
bucket.cpp:36:13: warning: unused variable 'k' [-Wunused-variable]
   36 |         int k;
      |             ^

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 34 / 34
• Subtask 4: 43 / 43