답안 #1100753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1100753	2024-10-14T15:28:03 Z	Uniq0rn	Mecho (IOI09_mecho)	C++14	0 / 100	195 ms	6616 KB

mecho

#include <bits/stdc++.h>
using namespace std;
 
#define ld long double 
#define ll long long int
#define pi pair<int,int>
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)
 
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n,s;cin >> n >> s;
    vector<vector<char>> a(n + 1,vector<char>(n + 1));
    queue<pair<int,int>> qu;
    vector<vector<int>> bdist(n + 1,vector<int>(n + 1));
    vector<vector<bool>> bvis(n + 1,vector<bool>(n + 1));
    int si = -1,sj = -1,ei = -1,ej = -1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin >> a[i][j];
            if(a[i][j] == 'H'){
                bvis[i][j] = true;
                qu.push({i,j});
            }
            if(a[i][j] == 'M'){
                si = i;
                sj = j;
            }
            if(a[i][j] == 'D'){
                ei = i;
                ej = j;
            }
        }
    }
    while(sz(qu)){
        int ni = qu.front().first,nj = qu.front().second;
        //cout << ni << ' ' << nj << '\n';
        qu.pop();
        for(int i=-1;i<=1;i++) for(int j=-1;j<=1;j++){
            if(abs(i) == abs(j)) continue;
            int ii = ni + i,jj = nj + j;
            if(ii < 1 || ii > n || jj < 1 || jj > n) continue;
            if(bvis[ii][jj] || a[ii][jj] == 'T' || a[ii][jj] == 'D') continue;
            bvis[ii][jj] = true;
            bdist[ii][jj] = bdist[ni][nj] + 1;
            qu.push({ii,jj});
        }
    }
    /*
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout << (bdist[i][j] == 1e9 ? -1 : bdist[i][j]) << ' ';
        }
        cout << '\n';
    }
    cout << "---------------------------------------------\n";
    */
    int ans = -1;
    int l = 0,r = n * n;
    while(l <= r){
        int mid = (l + r) >> 1;
        cout << mid << '\n';
        vector<vector<int>> dist(n + 1,vector<int>(n + 1));
        vector<vector<bool>> vis(n + 1,vector<bool>(n + 1));
        queue<pair<int,int>> q;
        q.push({si,sj});
        vis[si][sj] = true;
        bool ok = false;
        while(sz(q)){
            int ni = q.front().first,nj = q.front().second;
            q.pop();
            for(int i=-1;i<=1;i++) for(int j=-1;j<=1;j++){
                if(abs(i) == abs(j)) continue;
                int ii = ni + i,jj = nj + j;
                if(ii < 1 || ii > n || jj < 1 || jj > n) continue;
                if(vis[ii][jj]) continue;
                if(a[ii][jj] == 'T' || a[ii][jj] == 'H') continue;
                if(bdist[ii][jj] <= mid + (dist[ni][nj] + 1) / s) continue;
                vis[ii][jj] = true;
                dist[ii][jj] = dist[ni][nj] + 1;
                q.push({ii,jj});
            }
        }
        for(int i=-1;i<=1;i++) for(int j=-1;j<=1;j++){
            if(abs(i) == abs(j)) continue;
            int ii = ei + i,jj = ej + j;
            if(ii < 1 || ii > n || jj < 1 || jj > n) continue;
            if(a[ii][jj] == 'T' || a[ii][jj] == 'H') continue;
            if(!vis[ii][jj]) continue;
            if(dist[ii][jj] / s + mid >= bdist[ii][jj]) continue;
            ok = true;
        }
        /*
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                cout << dist[i][j] << ' ';
            }
            cout << '\n';
        }
        */
        if(ok){
            l = mid + 1;
            ans = mid;
        }
        else r = mid - 1;
    }
    cout << ans;
    /*
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout << bdist[i][j] << ' ';
        }
        cout << '\n';
    }
    */
    return 0;
}

Subtask #1

0.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	336 KB	Output isn't correct
2	Incorrect	0 ms	336 KB	Output isn't correct
3	Incorrect	1 ms	336 KB	Output isn't correct
4	Incorrect	1 ms	336 KB	Output isn't correct
5	Incorrect	1 ms	336 KB	Output isn't correct
6	Incorrect	1 ms	336 KB	Output isn't correct
7	Incorrect	103 ms	6456 KB	Output isn't correct
8	Incorrect	1 ms	336 KB	Output isn't correct
9	Incorrect	1 ms	336 KB	Output isn't correct
10	Incorrect	1 ms	336 KB	Output isn't correct
11	Incorrect	1 ms	336 KB	Output isn't correct
12	Incorrect	1 ms	336 KB	Output isn't correct
13	Incorrect	1 ms	336 KB	Output isn't correct
14	Incorrect	1 ms	336 KB	Output isn't correct
15	Incorrect	1 ms	336 KB	Output isn't correct
16	Incorrect	1 ms	336 KB	Output isn't correct
17	Incorrect	1 ms	336 KB	Output isn't correct
18	Incorrect	1 ms	504 KB	Output isn't correct
19	Incorrect	1 ms	336 KB	Output isn't correct
20	Incorrect	1 ms	348 KB	Output isn't correct
21	Incorrect	1 ms	336 KB	Output isn't correct
22	Incorrect	1 ms	336 KB	Output isn't correct
23	Incorrect	1 ms	336 KB	Output isn't correct
24	Incorrect	1 ms	336 KB	Output isn't correct
25	Incorrect	1 ms	336 KB	Output isn't correct
26	Incorrect	1 ms	336 KB	Output isn't correct
27	Incorrect	1 ms	336 KB	Output isn't correct
28	Incorrect	1 ms	336 KB	Output isn't correct
29	Incorrect	1 ms	504 KB	Output isn't correct
30	Incorrect	1 ms	336 KB	Output isn't correct
31	Incorrect	1 ms	336 KB	Output isn't correct
32	Incorrect	1 ms	336 KB	Output isn't correct
33	Incorrect	6 ms	1616 KB	Output isn't correct
34	Incorrect	6 ms	1616 KB	Output isn't correct
35	Incorrect	24 ms	1672 KB	Output isn't correct
36	Incorrect	8 ms	2128 KB	Output isn't correct
37	Incorrect	8 ms	1872 KB	Output isn't correct
38	Incorrect	32 ms	2012 KB	Output isn't correct
39	Incorrect	8 ms	2584 KB	Output isn't correct
40	Incorrect	10 ms	2412 KB	Output isn't correct
41	Incorrect	48 ms	2384 KB	Output isn't correct
42	Incorrect	11 ms	2740 KB	Output isn't correct
43	Incorrect	13 ms	2840 KB	Output isn't correct
44	Incorrect	53 ms	2840 KB	Output isn't correct
45	Incorrect	13 ms	3288 KB	Output isn't correct
46	Incorrect	15 ms	3340 KB	Output isn't correct
47	Incorrect	58 ms	3352 KB	Output isn't correct
48	Incorrect	14 ms	3836 KB	Output isn't correct
49	Incorrect	19 ms	3676 KB	Output isn't correct
50	Incorrect	70 ms	3868 KB	Output isn't correct
51	Incorrect	15 ms	4432 KB	Output isn't correct
52	Incorrect	18 ms	4432 KB	Output isn't correct
53	Incorrect	86 ms	4432 KB	Output isn't correct
54	Incorrect	20 ms	4944 KB	Output isn't correct
55	Incorrect	22 ms	4944 KB	Output isn't correct
56	Incorrect	117 ms	5064 KB	Output isn't correct
57	Incorrect	22 ms	5712 KB	Output isn't correct
58	Incorrect	28 ms	5712 KB	Output isn't correct
59	Incorrect	120 ms	5736 KB	Output isn't correct
60	Incorrect	27 ms	6264 KB	Output isn't correct
61	Incorrect	33 ms	6420 KB	Output isn't correct
62	Incorrect	133 ms	6576 KB	Output isn't correct
63	Incorrect	107 ms	6580 KB	Output isn't correct
64	Incorrect	195 ms	6440 KB	Output isn't correct
65	Incorrect	153 ms	6440 KB	Output isn't correct
66	Incorrect	129 ms	6468 KB	Output isn't correct
67	Incorrect	121 ms	6436 KB	Output isn't correct
68	Incorrect	77 ms	6552 KB	Output isn't correct
69	Incorrect	76 ms	6536 KB	Output isn't correct
70	Incorrect	64 ms	6460 KB	Output isn't correct
71	Incorrect	68 ms	6484 KB	Output isn't correct
72	Incorrect	54 ms	6616 KB	Output isn't correct
73	Incorrect	67 ms	6500 KB	Output isn't correct
74	Incorrect	83 ms	6476 KB	Output isn't correct
75	Incorrect	105 ms	6500 KB	Output isn't correct
76	Incorrect	85 ms	6468 KB	Output isn't correct
77	Incorrect	86 ms	6512 KB	Output isn't correct
78	Incorrect	104 ms	6392 KB	Output isn't correct
79	Incorrect	75 ms	6404 KB	Output isn't correct
80	Incorrect	82 ms	6280 KB	Output isn't correct
81	Incorrect	96 ms	6420 KB	Output isn't correct
82	Incorrect	87 ms	6464 KB	Output isn't correct
83	Incorrect	96 ms	6504 KB	Output isn't correct
84	Incorrect	92 ms	6456 KB	Output isn't correct
85	Incorrect	93 ms	6492 KB	Output isn't correct
86	Incorrect	102 ms	6436 KB	Output isn't correct
87	Incorrect	108 ms	6448 KB	Output isn't correct
88	Incorrect	98 ms	6480 KB	Output isn't correct
89	Incorrect	98 ms	6504 KB	Output isn't correct
90	Incorrect	103 ms	6452 KB	Output isn't correct
91	Incorrect	100 ms	6480 KB	Output isn't correct
92	Incorrect	107 ms	6488 KB	Output isn't correct