oj.uz

답안 #465433

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
465433 2021-08-16T04:02:51 Z NhatMinh0208 Soccer (JOI17_soccer) C++17
100 / 100
 963 ms 131580 KB 
#ifndef CPL_TEMPLATE
#define CPL_TEMPLATE
/*
	Normie's Template v2.5
	Changes:
    Added warning against using pragmas on USACO.
*/
// Standard library in one include.
#include <bits/stdc++.h>
using namespace std;
 
// ordered_set library.
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set(el) tree<el,null_type,less<el>,rb_tree_tag,tree_order_statistics_node_update>
 
// AtCoder library. (Comment out these two lines if you're not submitting in AtCoder.) (Or if you want to use it in other judges, run expander.py first.)
//#include <atcoder/all>
//using namespace atcoder;

//Pragmas (Comment out these three lines if you're submitting in szkopul or USACO.)
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,unroll-loops,tree-vectorize")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
 
//File I/O.
#define FILE_IN "cseq.inp"
#define FILE_OUT "cseq.out"
#define ofile freopen(FILE_IN,"r",stdin);freopen(FILE_OUT,"w",stdout)
 
//Fast I/O.
#define fio ios::sync_with_stdio(0);cin.tie(0)
#define nfio cin.tie(0)
#define endl "\n"
 
//Order checking.
#define ord(a,b,c) ((a>=b)and(b>=c))
 
//min/max redefines, so i dont have to resolve annoying compile errors.
#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))

// Fast min/max assigns to use with AVX.
// Requires g++ 9.2.0.
template<typename T>
__attribute__((always_inline)) void chkmin(T& a, const T& b) {
    a=(a<b)?a:b;
}

template<typename T>
__attribute__((always_inline)) void chkmax(T& a, const T& b) {
    a=(a>b)?a:b;
}
 
//Constants.
#define MOD (ll(998244353))
#define MAX 300001
#define mag 320
const long double PI=3.14159265358979;
 
//Pairs and 3-pairs.
#define p1 first
#define p2 second.first
#define p3 second.second
#define fi first
#define se second
#define pii(element_type) pair<element_type,element_type>
#define piii(element_type) pair<element_type,pii(element_type)>
 
//Quick power of 2.
#define pow2(x) (ll(1)<<x)
 
//Short for-loops.
#define ff(i,__,___) for(int i=__;i<=___;i++)
#define rr(i,__,___) for(int i=__;i>=___;i--)
 
//Typedefs.
#define bi BigInt
typedef long long ll;
typedef long double ld;
typedef short sh;

// Binpow and stuff
ll BOW(ll a, ll x, ll p)
{
	if (!x) return 1;
	ll res=BOW(a,x/2,p);
	res*=res;
	res%=p;
	if (x%2) res*=a;
	return res%p;
}
ll INV(ll a, ll p)
{
	return BOW(a,p-2,p);
}
//---------END-------//
#endif
vector<pii(ll)> gt[1300001];
ll n,m,i,j,k,t,t1,u,v,a,b;
ll A,B,C;
ll dis[1300001];
ll res[1300001];
ll px[100001],py[100001];
priority_queue<pii(ll),vector<pii(ll)>,greater<pii(ll)>> pq;
int main()
{
	fio;
    cin>>n>>m;
    n++;
    m++;
    cin>>A>>B>>C;
    for (i=0;i<n;i++) for (j=0;j<m;j++)
    {
        if (i+1<n)
        {
            gt[i*m+j].push_back({C,i*m+j+m});
            gt[i*m+j+m].push_back({C,i*m+j});
        }
        if (j+1<m)
        {
            gt[i*m+j+1].push_back({C,i*m+j});
            gt[i*m+j].push_back({C,i*m+j+1});
        }
    }
    for (i=0;i<n;i++) for (j=0;j<m;j++)
    {
        dis[i*m+j]=1e18;
    }

    cin>>t;
    for (t1=0;t1<t;t1++)
    {
        cin>>px[t1]>>py[t1];
        dis[px[t1]*m+py[t1]]=0;
        pq.push({0,px[t1]*m+py[t1]});
    }
    while(pq.size())
    {
        auto pp = pq.top();
        pq.pop();
        if (dis[pp.se]<pp.fi) continue;
        for (auto g : gt[pp.se])
        {
            if (dis[g.se]>g.fi+pp.fi)
            {
                dis[g.se]=g.fi+pp.fi;
                pq.push({dis[g.se],g.se});
            }
        }
    }

    for (i=0;i<n;i++) for (j=0;j<m;j++)
    {
        gt[m*n+i*m+j].push_back({dis[i*m+j],i*m+j});
        gt[2*m*n+i*m+j].push_back({dis[i*m+j],i*m+j});
        gt[3*m*n+i*m+j].push_back({dis[i*m+j],i*m+j});
        gt[4*m*n+i*m+j].push_back({dis[i*m+j],i*m+j});
        if (i)
        {
            gt[i*m+j].push_back({A+B,m*n+i*m+j-m});
            gt[m*n+i*m+j].push_back({A,m*n+i*m+j-m});
        }
        if (i+1<n)
        {
            gt[i*m+j].push_back({A+B,2*m*n+i*m+j+m});
            gt[2*m*n+i*m+j].push_back({A,2*m*n+i*m+j+m});
        }
        if (j)
        {
            gt[i*m+j].push_back({A+B,3*m*n+i*m+j-1});
            gt[3*m*n+i*m+j].push_back({A,3*m*n+i*m+j-1});
        }
        if (j+1<m)
        {
            gt[i*m+j].push_back({A+B,4*m*n+i*m+j+1});
            gt[4*m*n+i*m+j].push_back({A,4*m*n+i*m+j+1});
        }
        res[i*m+j]=1e18;
        res[m*n+i*m+j]=1e18;
        res[2*m*n+i*m+j]=1e18;
        res[3*m*n+i*m+j]=1e18;
        res[4*m*n+i*m+j]=1e18;
    }

        res[px[0]*m+py[0]]=0;
        pq.push({0,px[0]*m+py[0]});

    while(pq.size())
    {
        auto pp = pq.top();
        pq.pop();
        if (res[pp.se]<pp.fi) continue;
        for (auto g : gt[pp.se])
        {
            if (res[g.se]>g.fi+pp.fi)
            {
                res[g.se]=g.fi+pp.fi;
                pq.push({res[g.se],g.se});
            }
        }
    }
    a=1e18;
    a=min(a,res[px[t-1]*m+py[t-1]]);
    a=min(a,res[m*n+px[t-1]*m+py[t-1]]);
    a=min(a,res[2*m*n+px[t-1]*m+py[t-1]]);
    a=min(a,res[3*m*n+px[t-1]*m+py[t-1]]);
    a=min(a,res[4*m*n+px[t-1]*m+py[t-1]]);
    cout<<a;
}
// Normie28

Compilation message

soccer.cpp:23: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
   23 | #pragma comment(linker, "/stack:200000000")
      |

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 162 ms 54716 KB Output is correct
2 Correct 19 ms 30924 KB Output is correct
3 Correct 646 ms 129256 KB Output is correct
4 Correct 719 ms 129440 KB Output is correct
5 Correct 176 ms 65476 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 739 ms 129248 KB Output is correct
2 Correct 727 ms 129228 KB Output is correct
3 Correct 538 ms 110512 KB Output is correct
4 Correct 562 ms 129328 KB Output is correct
5 Correct 592 ms 110492 KB Output is correct
6 Correct 617 ms 129340 KB Output is correct
7 Correct 709 ms 129196 KB Output is correct
8 Correct 662 ms 129276 KB Output is correct
9 Correct 713 ms 129300 KB Output is correct
10 Correct 110 ms 47268 KB Output is correct
11 Correct 773 ms 129216 KB Output is correct
12 Correct 766 ms 129232 KB Output is correct
13 Correct 450 ms 110516 KB Output is correct
14 Correct 730 ms 129236 KB Output is correct
15 Correct 562 ms 110516 KB Output is correct

Subtask #3
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 162 ms 54716 KB Output is correct
2 Correct 19 ms 30924 KB Output is correct
3 Correct 646 ms 129256 KB Output is correct
4 Correct 719 ms 129440 KB Output is correct
5 Correct 176 ms 65476 KB Output is correct
6 Correct 739 ms 129248 KB Output is correct
7 Correct 727 ms 129228 KB Output is correct
8 Correct 538 ms 110512 KB Output is correct
9 Correct 562 ms 129328 KB Output is correct
10 Correct 592 ms 110492 KB Output is correct
11 Correct 617 ms 129340 KB Output is correct
12 Correct 709 ms 129196 KB Output is correct
13 Correct 662 ms 129276 KB Output is correct
14 Correct 713 ms 129300 KB Output is correct
15 Correct 110 ms 47268 KB Output is correct
16 Correct 773 ms 129216 KB Output is correct
17 Correct 766 ms 129232 KB Output is correct
18 Correct 450 ms 110516 KB Output is correct
19 Correct 730 ms 129236 KB Output is correct
20 Correct 562 ms 110516 KB Output is correct
21 Correct 230 ms 65468 KB Output is correct
22 Correct 907 ms 129184 KB Output is correct
23 Correct 817 ms 117904 KB Output is correct
24 Correct 963 ms 127240 KB Output is correct
25 Correct 785 ms 129412 KB Output is correct
26 Correct 768 ms 129456 KB Output is correct
27 Correct 544 ms 128640 KB Output is correct
28 Correct 655 ms 129552 KB Output is correct
29 Correct 738 ms 129088 KB Output is correct
30 Correct 587 ms 128952 KB Output is correct
31 Correct 826 ms 129360 KB Output is correct
32 Correct 940 ms 131580 KB Output is correct
33 Correct 643 ms 129384 KB Output is correct
34 Correct 919 ms 129252 KB Output is correct
35 Correct 551 ms 129008 KB Output is correct