Submission #140774

#	Time	Username	Problem	Language	Result	Execution time	Memory
140774		khrbuddy03	물통 (KOI17_bucket)	C++14	100 / 100	651 ms	24396 KiB

bucket

#include <bits/stdc++.h>

using namespace std;

map<pair<int, int>, bool> vis;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int X, Y, A, B; cin >> X >> Y >> A >> B;
    queue<pair<int, pair<int, int>>> q;
    q.push(make_pair(0, make_pair(0, 0)));
    vis[make_pair(0, 0)] = true;
    while (!q.empty()) {
        int dist = q.front().first;
        int a = q.front().second.first, b = q.front().second.second;
        // cout << dist << ' ' << a << ' ' << b << '\n';
        q.pop();
        if (a == A && b == B) {
            cout << dist << '\n';
            return 0;
        }
        pair<int, int> next[6] = {{a, Y}, {X, b}, {a - min(a, Y - b), b + min(a, Y - b)}, {a + min(b, X - a), b - min(b, X - a)}, {a, 0}, {0, b}};
        for (int i = 0; i < 6; i++) {
            if (vis[next[i]]) continue;
            q.push(make_pair(dist + 1, next[i]));
            vis[next[i]] = true;
        }
    }
    cout << "-1\n";
}

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