Submission #225475

#	Time	Username	Problem	Language	Result	Execution time	Memory
225475		Ruxandra985	Soccer (JOI17_soccer)	C++14	100 / 100	377 ms	26728 KiB

soccer

#include <bits/stdc++.h>
#define INF 2000000000000000000
using namespace std;
long long di[] = {0 , 0 , 0 , 1 , -1};
long long dj[] = {0 , 1 , -1 , 0 , 0};
priority_queue <pair <pair <long long,long long> , pair <long long,long long> > > h;
pair <long long,long long> v[100010];
deque <pair <long long,long long> > dq;
long long f[510][510];
long long dp[510][510][6];
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    long long n , m , a , b , c , k , ic , jc , iv , jv , dirc , dirv , i , j , val , d;
    fscanf (fin,"%lld%lld%lld%lld%lld%lld",&n,&m,&a,&b,&c,&k);
    n++;
    m++;
    for (i = 1 ; i <= k ; i++){
        fscanf (fin,"%lld%lld",&v[i].first,&v[i].second);
        v[i].first++;
        v[i].second++;
        if (i != k){ /// modifica aici daca vrei sa se plimbe si k
            dq.push_back(v[i]);
            f[v[i].first][v[i].second] = 1;
        }
    }

    while (!dq.empty()){

        ic = dq.front().first;
        jc = dq.front().second;
        dq.pop_front();

        for (d = 1 ; d <= 4 ; d++){
            iv = ic + di[d];
            jv = jc + dj[d];

            if (iv > 0 && jv > 0 && iv <= n && jv <= m && !f[iv][jv]){
                f[iv][jv] = 1 + f[ic][jc];
                dq.push_back(make_pair(iv , jv));
            }

        }

    }

    /// f[i][j] - 1 = distanta minima de la orice jucator (in afr de k) la i j

    /// dp[i][j][dir] = cost minim sa ajungi in i j si directia sa fie dir
    /// dir = 0 => apartine unui jucator

    for (i = 1 ; i <= n ; i++){
        for (j = 1 ; j <= m ; j++){
            for (d = 0 ; d < 5 ; d++)
                dp[i][j][d] = INF;
        }
    }


    dp[v[1].first][v[1].second][0] = 0; /// stare initiala
    h.push(make_pair( make_pair(0 , 0) , v[1] ) );

    while (!h.empty()){

        val = -h.top().first.first;
        dirc = h.top().first.second;
        ic = h.top().second.first;
        jc = h.top().second.second;
        h.pop();

        //if (ic == 2 && jc == 5 && dirc == 1)
          //  printf ("a");

        if (dp[ic][jc][dirc] != val)
            continue;

        //printf ("%lld %lld %lld\n" , ic , jc , dirc);

        if (ic == v[k].first && jc == v[k].second){

            fprintf (fout,"%lld",val);
            return 0;

        }

        if (dirc != 0){ /// nu apartine niciunui jucator si e intr un sut

            /// cazul 1 : un jucator o sa vina sa o ia aici

            dirv = 0;
            iv = ic;
            jv = jc;
            if (dp[iv][jv][dirv] > dp[ic][jc][dirc] + c * ( f[iv][jv] - 1 ) ){
                dp[iv][jv][dirv] = dp[ic][jc][dirc] + c * ( f[iv][jv] - 1 );
                h.push(make_pair( make_pair(-dp[iv][jv][dirv] , dirv) , make_pair(iv , jv) ) );
            }

            /// cazul 2 : continua pe directia aia

            dirv = dirc;
            iv = ic + di[dirc];
            jv = jc + dj[dirc];
            if (iv > 0 && jv > 0 && iv <= n && jv <= m && dp[iv][jv][dirv] > dp[ic][jc][dirc] + a ){
                dp[iv][jv][dirv] = dp[ic][jc][dirc] + a;
                h.push(make_pair( make_pair(-dp[iv][jv][dirv] , dirv) , make_pair(iv , jv) ) );
            }


        }
        else {

            /// acum apartine unui jucator
            /// cazul 1 : jucatorul asta face un pas cu ea

            dirv = 0;

            for (d = 1 ; d < 5 ; d++){
                iv = ic + di[d];
                jv = jc + dj[d];

                if (iv > 0 && jv > 0 && iv <= n && jv <= m && dp[iv][jv][dirv] > dp[ic][jc][dirc] + c ){
                    dp[iv][jv][dirv] = dp[ic][jc][dirc] + c;
                    h.push(make_pair( make_pair(-dp[iv][jv][dirv] , dirv) , make_pair(iv , jv) ) );
                }

            }

            /// cazul 2 : jucatorul care o are acum ii da un sut intr o directie

            for (d = 1 ; d < 5 ; d++){
                iv = ic + di[d];
                jv = jc + dj[d];
                dirv = d;

                if (iv > 0 && jv > 0 && iv <= n && jv <= m && dp[iv][jv][dirv] > dp[ic][jc][dirc] + a + b ){
                    dp[iv][jv][dirv] = dp[ic][jc][dirc] + a + b;
                    h.push(make_pair( make_pair(-dp[iv][jv][dirv] , dirv) , make_pair(iv , jv) ) );
                }

            }


        }

    }


    return 0;
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:16:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%lld%lld%lld%lld%lld%lld",&n,&m,&a,&b,&c,&k);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:20:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%lld%lld",&v[i].first,&v[i].second);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65