Submission #58998

#	Time	Username	Problem	Language	Result	Execution time	Memory
58998		andy627	물통 (KOI17_bucket)	C++17	100 / 100	472 ms	24916 KiB

bucket

#include <stdio.h>
#include <queue>
#include <map>
#include <algorithm>
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;

map<pii,int> mp;
queue<pii> q;

int main(){
    int a,b,c,d;

    scanf("%d %d %d %d",&a,&b,&c,&d);
    if(a!=c && c && b!=d && d){printf("-1");return 0;}
    if(c==0 && d==0){printf("0");return 0;}

    mp[{0,0}]=0; q.push({0,0});
    while(!q.empty()){
        int pa=q.front().ff;
        int pb=q.front().ss; q.pop();
        int pd=mp[{pa,pb}];

        if(pa==c && pb==d){printf("%d",pd);return 0;}

        if(pa && mp.find({0,pb})==mp.end()) mp[{0,pb}]=pd+1,q.push({0,pb});
        if(pb && mp.find({pa,0})==mp.end()) mp[{pa,0}]=pd+1,q.push({pa,0});
        if(pa!=a){
            if(mp.find({a,pb})==mp.end()) mp[{a,pb}]=pd+1,q.push({a,pb});
            if(pa+pb>a && mp.find({a,pa+pb-a})==mp.end()) mp[{a,pa+pb-a}]=pd+1,q.push({a,pa+pb-a});
            if(pa+pb<=a && mp.find({pa+pb,0})==mp.end()) mp[{pa+pb,0}]=pd+1,q.push({pa+pb,0});
        }
        if(pb!=b){
            if(mp.find({pa,b})==mp.end()) mp[{pa,b}]=pd+1,q.push({pa,b});
            if(pa+pb>b && mp.find({pa+pb-b,b})==mp.end()) mp[{pa+pb-b,b}]=pd+1,q.push({pa+pb-b,b});
            if(pa+pb<=b && mp.find({0,pa+pb})==mp.end()) mp[{0,pa+pb}]=pd+1,q.push({0,pa+pb});
        }

        //printf("%d %d %d\n",q.front().ff,q.front().ss,q.size());
    }

    printf("-1");

    return 0;
}

Compilation message (stderr)

bucket.cpp: In function 'int main()':
bucket.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d",&a,&b,&c,&d);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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