Submission #631918

#	Time	Username	Problem	Language	Result	Execution time	Memory
631918		minhcool	버스 (JOI14_bus)	C++17	0 / 100	117 ms	192860 KiB

bus

#include<bits/stdc++.h>
using namespace std;
 
#define y1 y11
#define int long long
#define fi first
#define se second
#define pb push_back
//#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
 
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, ii> iiii;
 
const int N = 1e3 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;

int w, h, n, stx, sty, enx, eny;
map<int, ii> options[N][N];// from (x, y) to one of four directions

int x[] = {0, 1, 0, -1};
int y[] = {1, 0, -1, 0};

bool vis[N][N];
map<int, int> mn_dist[N][N];

void dijik(){
    priority_queue<iiii, vector<iiii>, greater<iiii>> pq;
    /*
    for(int i = 1; i <= w; i++){
        for(int j = 1; j <= h; j++) mn_dist[i][j] = oo;
    }*/
    vector<int> b;
    for(auto it : mn_dist[stx][sty]) b.pb(it.fi);
    for(auto it : b){
        mn_dist[stx][sty][it] = 0;
        pq.push({{0, it}, {stx, sty}});
    }
    while(!pq.empty()){
        int d = pq.top().fi.fi, curbus = pq.top().fi.se, curx = pq.top().se.fi, cury = pq.top().se.se;
        pq.pop();
        if(d != mn_dist[curx][cury][curbus]) continue;
        if(!vis[curx][cury]){
            vis[curx][cury] = 1;
            b.clear();
            for(auto it : mn_dist[curx][cury]) b.pb(it.fi);
            for(auto it : b){
                //cout << stx << " " << sty << " " << it << " " << mn_dist[stx][sty][it] << "\n";
                if(mn_dist[curx][cury][it] > d + 1){
                    mn_dist[curx][cury][it] = d + 1;
                    pq.push({{mn_dist[curx][cury][it], it}, {curx, cury}});
                }
            }
        }
        ii temp = options[curx][cury][curbus];
       //cout << d << " " << curbus << " " << curx << " " << cury << "\n";
        for(int i = 0; i < 4; i++){
            int nxtx = curx + x[i], nxty = cury + y[i];
            if(mn_dist[nxtx][nxty].find(curbus) == mn_dist[nxtx][nxty].end()) continue;
            int mini = oo;
            int nxt = d - (d % temp.fi) + temp.se;
            if(nxt < d) nxt += temp.fi;
            mini = min(mini, nxt);
            mini++;
            if(mini < mn_dist[nxtx][nxty][curbus]){
                mn_dist[nxtx][nxty][curbus] = mini;
                pq.push({{mn_dist[nxtx][nxty][curbus], curbus}, {nxtx, nxty}});
            }
        }
    }
}
 
void process(){
    cin >> h >> w >> sty >> stx >> eny >> enx;
    cin >> n;
    for(int i = 1; i <= n; i++){
        int x1, y1, x2, y2, t;
        cin >> x1 >> y1 >> x2 >> y2 >> t;
        swap(x1, y1), swap(x2, y2);
        int cnt = 0, itrx = x1, itry = y1, cur = 0;
        int peri = (x2 - x1 + y2 - y1) * 2;
        for(int j = 0; j < peri; j++){
            mn_dist[itrx][itry][i] = oo;
            int nxtx = itrx + x[cur], nxty = itry + y[cur];
            //cout << i << " " << j << " " << itrx << " " << itry << "\n";
            if(nxtx < x1 || nxtx > x2 || nxty < y1 || nxty > y2) cur++;
            assert(cur <= 3);
            nxtx = itrx + x[cur], nxty = itry + y[cur];
            int fi_trip;
            if(j < t) fi_trip = peri - (t - j);
            else fi_trip = j - t;
            options[itrx][itry][i] = {peri, fi_trip};
            itrx += x[cur], itry += y[cur];
        }
    }
    //return;
    dijik();
    int ans = oo;
    for(auto it : mn_dist[enx][eny]) ans = min(ans, it.se);
    cout << ans;
    //cout << mn_dist[enx][eny];
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	int t = 1;
	//cin >> t;
	while(t--) process();
}

Compilation message (stderr)

bus.cpp: In function 'void process()':
bus.cpp:83:13: warning: unused variable 'cnt' [-Wunused-variable]
   83 |         int cnt = 0, itrx = x1, itry = y1, cur = 0;
      |             ^~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 50