답안 #969025

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
969025	2024-04-24T11:49:06 Z	anango	Mecho (IOI09_mecho)	C++17	20 / 100	746 ms	26396 KB

mecho

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,s;
vector<vector<int>> dist;
vector<vector<int>> grid;
pair<int,int> start;
pair<int,int> finish;


int INF=1000000007;
int gval(pair<int,int> cell) {
    return grid[cell.first][cell.second];
}

bool bounds(pair<int,int> cell) {
    return 0<=cell.first && cell.first<n && 0<=cell.second && cell.second<n;
}

vector<pair<int,int>> getnei(pair<int,int> st) {
    if (!(gval(st)==0 || gval(st)==3)) {
        return {};
    }
    vector<pair<int,int>> V={{st.first-1,st.second},{st.first+1,st.second},{st.first,st.second+1},{st.first,st.second-1}};
    vector<pair<int,int>> ans;
    for (auto nei:V) {
        if (bounds(nei) && ((gval(nei)==0) || gval(nei)==2)) {
            ans.push_back(nei);
        }
    }
    return ans;
}

bool BSTA(int time) {
    //returns whether it can be done after waiting this time
    vector<vector<int>> distance(n,vector<int>(n,INF));
    vector<vector<int>> proc(n,vector<int>(n,0));
    deque<pair<int,int>> visited={start};
    distance[start.first][start.second] = 0;
    while (visited.size()) {
        pair<int,int> fi=visited[0];
        visited.pop_front();
        if (proc[fi.first][fi.second]) {
            continue;
        }
        proc[fi.first][fi.second] = 1;
        for (auto j:getnei(fi)) {
            int bdist=(distance[fi.first][fi.second]+s-1)/s + time; //ceil(distance/S)+T
            //cout << fi.first << " " << fi.second << " " << j.first << " " << j.second << " "<<bdist << " " <<dist[fi.first][fi.second] << endl;
            if (bdist>dist[fi.first][fi.second]) {
                continue;
            }
            distance[j.first][j.second] = min(distance[j.first][j.second],distance[fi.first][fi.second]+1);
            visited.push_back(j);
        }
    }
    //cout << "BSTA TRYING METHOD CALCULATION TO FIND THE ANSWER" << " " << time << endl;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            //cout << distance[i][j] <<" ";
        }
        //cout << endl;
    }
    return distance[finish.first][finish.second] < 3*n;
    
}


vector<pair<int,int>> adjlistbee(pair<int,int> st) {
    if (!(gval(st)==0 || gval(st)==3)) {
        return {};
    }
    vector<pair<int,int>> V={{st.first-1,st.second},{st.first+1,st.second},{st.first,st.second+1},{st.first,st.second-1}};
    vector<pair<int,int>> ans;
    for (auto nei:V) {
        if (bounds(nei) && gval(nei)==0) {
            ans.push_back(nei);
        }
    }
    return ans;
}

signed main() {
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    cin >> n >> s;
    dist=vector<vector<int>>(n,vector<int>(n,INF));
    grid=vector<vector<int>>(n,vector<int>(n,-1));
    vector<vector<int>> proc(n,vector<int>(n,0));
    vector<pair<int,int>> hives;
    deque<pair<int,int>> visited;
    for (int i=0; i<n; i++) {
        string st;
        cin >> st;
        ////cout << st << endl;
        for (int j=0; j<n; j++) {
            ////cout << i <<" " << j << " " << st[j] << endl;
            int ans;
            if (st[j]=='G') {
                ans=0;
            }
            else if (st[j]=='M') {
                ans=0;
                start={i,j};
            }
            else if (st[j]=='D') {
                ans=2;
                finish={i,j};
            }
            else if (st[j]=='T') {
                ans=1;
                
            }
            else {
                //assert(st[j]=='H');
                ans=3;
                hives.push_back({i,j});
                dist[i][j] = 0;
                visited.push_back({i,j});
            }
            grid[i][j] = ans;
            ////cout << i << " " << j << endl;
        }
    }
    //a cell is available to bees if the cell is 0 or 3, 3 denotes starting hives
    //a cell is available to mecho if the dist condition holds and the cell isn't a tree
    while (visited.size()) {
        pair<int,int> fi=visited[0];
        visited.pop_front();
        if (proc[fi.first][fi.second]) {
            continue;
        }
        proc[fi.first][fi.second] = 1;
        for (auto j:adjlistbee(fi)) {
            dist[j.first][j.second] = min(dist[j.first][j.second],dist[fi.first][fi.second]+1);
            visited.push_back(j);
        }
    }
    //cout << "DISTS"<< endl;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            //cout << dist[i][j] <<" ";
        }
        //cout << endl;
    }
    


    int l=0;
    int r=n*3;
    while (l<r) {
        int m=(l+r)/2;
        if (!BSTA(m)) {
            l=l;
            r=m;
        }
        else {
            l=m+1;
            r=r;
        }
    }
    if (l==0 && !BSTA(l)) {
        //cout << -1 << endl;
        return 0;
    }
    cout << l-1 << endl;

}

Subtask #1

20.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	344 KB	Output isn't correct
2	Incorrect	1 ms	348 KB	Output isn't correct
3	Incorrect	0 ms	348 KB	Output isn't correct
4	Incorrect	1 ms	348 KB	Output isn't correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	411 ms	25856 KB	Output is correct
8	Incorrect	0 ms	344 KB	Output isn't correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	432 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Incorrect	1 ms	348 KB	Output isn't correct
13	Incorrect	1 ms	348 KB	Output isn't correct
14	Incorrect	2 ms	348 KB	Output isn't correct
15	Incorrect	0 ms	432 KB	Output isn't correct
16	Incorrect	1 ms	348 KB	Output isn't correct
17	Incorrect	0 ms	348 KB	Output isn't correct
18	Incorrect	0 ms	436 KB	Output isn't correct
19	Incorrect	1 ms	348 KB	Output isn't correct
20	Incorrect	1 ms	348 KB	Output isn't correct
21	Incorrect	1 ms	348 KB	Output isn't correct
22	Incorrect	1 ms	348 KB	Output isn't correct
23	Incorrect	1 ms	348 KB	Output isn't correct
24	Incorrect	1 ms	348 KB	Output isn't correct
25	Incorrect	1 ms	348 KB	Output isn't correct
26	Incorrect	2 ms	344 KB	Output isn't correct
27	Incorrect	1 ms	604 KB	Output isn't correct
28	Incorrect	2 ms	616 KB	Output isn't correct
29	Incorrect	1 ms	604 KB	Output isn't correct
30	Incorrect	2 ms	604 KB	Output isn't correct
31	Incorrect	2 ms	604 KB	Output isn't correct
32	Incorrect	2 ms	604 KB	Output isn't correct
33	Incorrect	37 ms	5368 KB	Output isn't correct
34	Incorrect	56 ms	5392 KB	Output isn't correct
35	Correct	88 ms	5380 KB	Output is correct
36	Incorrect	48 ms	6876 KB	Output isn't correct
37	Incorrect	75 ms	6844 KB	Output isn't correct
38	Correct	127 ms	6856 KB	Output is correct
39	Incorrect	68 ms	8584 KB	Output isn't correct
40	Incorrect	94 ms	8580 KB	Output isn't correct
41	Correct	145 ms	8624 KB	Output is correct
42	Incorrect	74 ms	10496 KB	Output isn't correct
43	Incorrect	123 ms	10596 KB	Output isn't correct
44	Correct	185 ms	10380 KB	Output is correct
45	Incorrect	90 ms	12548 KB	Output isn't correct
46	Incorrect	163 ms	12588 KB	Output isn't correct
47	Correct	247 ms	12604 KB	Output is correct
48	Incorrect	107 ms	14888 KB	Output isn't correct
49	Incorrect	179 ms	14856 KB	Output isn't correct
50	Correct	305 ms	14788 KB	Output is correct
51	Incorrect	126 ms	17360 KB	Output isn't correct
52	Incorrect	210 ms	17732 KB	Output isn't correct
53	Correct	359 ms	17380 KB	Output is correct
54	Incorrect	169 ms	20040 KB	Output isn't correct
55	Incorrect	259 ms	20080 KB	Output isn't correct
56	Correct	440 ms	20064 KB	Output is correct
57	Incorrect	222 ms	22948 KB	Output isn't correct
58	Incorrect	292 ms	22936 KB	Output isn't correct
59	Correct	516 ms	23092 KB	Output is correct
60	Incorrect	208 ms	26064 KB	Output isn't correct
61	Incorrect	344 ms	26116 KB	Output isn't correct
62	Correct	660 ms	26376 KB	Output is correct
63	Incorrect	386 ms	26064 KB	Output isn't correct
64	Incorrect	746 ms	26040 KB	Output isn't correct
65	Incorrect	656 ms	26088 KB	Output isn't correct
66	Incorrect	558 ms	26140 KB	Output isn't correct
67	Incorrect	418 ms	26056 KB	Output isn't correct
68	Incorrect	194 ms	26144 KB	Output isn't correct
69	Incorrect	216 ms	26116 KB	Output isn't correct
70	Incorrect	221 ms	26180 KB	Output isn't correct
71	Incorrect	160 ms	26164 KB	Output isn't correct
72	Incorrect	113 ms	26200 KB	Output isn't correct
73	Incorrect	162 ms	26248 KB	Output isn't correct
74	Correct	278 ms	26180 KB	Output is correct
75	Correct	346 ms	26216 KB	Output is correct
76	Correct	324 ms	26168 KB	Output is correct
77	Correct	327 ms	26240 KB	Output is correct
78	Incorrect	428 ms	26136 KB	Output isn't correct
79	Correct	327 ms	26224 KB	Output is correct
80	Correct	300 ms	26104 KB	Output is correct
81	Correct	327 ms	26148 KB	Output is correct
82	Correct	287 ms	26084 KB	Output is correct
83	Correct	420 ms	26396 KB	Output is correct
84	Correct	335 ms	26016 KB	Output is correct
85	Correct	351 ms	26248 KB	Output is correct
86	Correct	387 ms	26152 KB	Output is correct
87	Correct	366 ms	26164 KB	Output is correct
88	Correct	408 ms	26140 KB	Output is correct
89	Correct	556 ms	26336 KB	Output is correct
90	Correct	443 ms	26224 KB	Output is correct
91	Correct	382 ms	26104 KB	Output is correct
92	Correct	411 ms	26388 KB	Output is correct