oj.uz

답안 #777270

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
777270 2023-07-09T01:17:07 Z bachhoangxuan Soccer (JOI17_soccer) C++17
35 / 100
 317 ms 38696 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<pii,int>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e18;
const int mod=1e9+7;
const int maxn=1005;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=500005;
const int maxl=20;
const int maxa=250000;
const int root=3;
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
const int iroot=power(3,mod-2);
const int base=101;
struct dd{
    int x,y,t,d;
    friend bool operator<(dd a,dd b){return a.d<b.d;}
    friend bool operator>(dd a,dd b){return a.d>b.d;}
};
int dx[]={0,0,1,-1},
    dy[]={1,-1,0,0};
int n,m,a,b,c,sz,f[maxn][maxn],dist[maxn][maxn][10];
void solve(){
    cin >> n >> m >> a >> b >> c >> sz;
    vector<pii> p(sz+1);
    memset(f,-1,sizeof(f));
    queue<pii> q;
    for(int i=1;i<=sz;i++){
        cin >> p[i].fi >> p[i].se;
        f[p[i].fi][p[i].se]=0;q.push(p[i]);
    }
    auto ok = [&](int x,int y){
        if(x<0 || y<0 || x>n || y>m) return false;
        return true;
    };
    while(!q.empty()){
        auto &[x,y]=q.front();q.pop();
        for(int t=0;t<4;t++){
            int xt=x+dx[t],yt=y+dy[t];
            if(ok(xt,yt) && f[xt][yt]==-1) f[xt][yt]=f[x][y]+1,q.push({xt,yt});
        }
    }
    /*
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++) cout << f[i][j] << ' ';
        cout << '\n';
    }
    */
    for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) for(int t=0;t<=4;t++) dist[i][j][t]=inf;
    priority_queue<dd,vector<dd>,greater<dd>> pq;
    dist[p[1].fi][p[1].se][4]=0;pq.push({p[1].fi,p[1].se,4,0});;
    while(!pq.empty()){
        auto [x,y,dir,d]=pq.top();pq.pop();
        if(d!=dist[x][y][dir]) continue;
        //cout << x << ' ' << y << ' ' << dir << ' ' << d << '\n';
        if(dir==4){
            for(int t=0;t<4;t++){
                int xt=x+dx[t],yt=y+dy[t];
                if(!ok(xt,yt)) continue;
                if(dist[xt][yt][t]>d+a+b){
                    dist[xt][yt][t]=d+a+b;
                    pq.push({xt,yt,t,d+a+b});
                }
                if(dist[xt][yt][4]>d+c){
                    dist[xt][yt][4]=d+c;
                    //cout << xt << ' ' << yt << ' ' << 4 << ' ' << d+c << '\n';
                    pq.push({xt,yt,4,d+c});
                }
            }
        }
        else{
            int xt=x+dx[dir],yt=y+dy[dir];
            if(ok(xt,yt) && dist[xt][yt][dir]>d+a){
                dist[xt][yt][dir]=d+a;
                pq.push({xt,yt,dir,d+a});
            }
            if(dist[x][y][4]>d+f[x][y]*c){
                dist[x][y][4]=d+f[x][y]*c;
                pq.push({x,y,4,d+f[x][y]*c});
            }
        }
    }
    cout << dist[p[sz].fi][p[sz].se][4] << '\n';
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 16332 KB Output is correct
2 Correct 3 ms 8276 KB Output is correct
3 Correct 245 ms 38176 KB Output is correct
4 Correct 270 ms 38160 KB Output is correct
5 Correct 36 ms 17104 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 264 ms 38208 KB Output is correct
2 Correct 262 ms 38208 KB Output is correct
3 Correct 181 ms 33848 KB Output is correct
4 Correct 184 ms 38192 KB Output is correct
5 Correct 208 ms 34360 KB Output is correct
6 Correct 209 ms 38240 KB Output is correct
7 Correct 267 ms 38428 KB Output is correct
8 Correct 239 ms 38200 KB Output is correct
9 Correct 313 ms 38388 KB Output is correct
10 Correct 35 ms 15688 KB Output is correct
11 Correct 253 ms 38520 KB Output is correct
12 Correct 259 ms 38276 KB Output is correct
13 Correct 169 ms 33860 KB Output is correct
14 Correct 289 ms 38364 KB Output is correct
15 Correct 188 ms 34400 KB Output is correct

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 16332 KB Output is correct
2 Correct 3 ms 8276 KB Output is correct
3 Correct 245 ms 38176 KB Output is correct
4 Correct 270 ms 38160 KB Output is correct
5 Correct 36 ms 17104 KB Output is correct
6 Correct 264 ms 38208 KB Output is correct
7 Correct 262 ms 38208 KB Output is correct
8 Correct 181 ms 33848 KB Output is correct
9 Correct 184 ms 38192 KB Output is correct
10 Correct 208 ms 34360 KB Output is correct
11 Correct 209 ms 38240 KB Output is correct
12 Correct 267 ms 38428 KB Output is correct
13 Correct 239 ms 38200 KB Output is correct
14 Correct 313 ms 38388 KB Output is correct
15 Correct 35 ms 15688 KB Output is correct
16 Correct 253 ms 38520 KB Output is correct
17 Correct 259 ms 38276 KB Output is correct
18 Correct 169 ms 33860 KB Output is correct
19 Correct 289 ms 38364 KB Output is correct
20 Correct 188 ms 34400 KB Output is correct
21 Correct 50 ms 17720 KB Output is correct
22 Correct 317 ms 38260 KB Output is correct
23 Correct 277 ms 32004 KB Output is correct
24 Correct 308 ms 34320 KB Output is correct
25 Correct 280 ms 38296 KB Output is correct
26 Correct 306 ms 38696 KB Output is correct
27 Runtime error 27 ms 22728 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -