oj.uz

Submission #723130

# Submission time Handle Problem Language Result Execution time Memory
723130 2023-04-13T09:03:54 Z rshohruh Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 15760 KB 
    #include <bits/stdc++.h>
     
    using namespace std;
     
    #define int long long
     
    signed main() {
        int n, m; cin >> n >> m;
        vector<int> s(n+1);
        for (int i = 1; i <= n; ++i) cin >> s[i];
        vector<vector<int>> ed(n+1);
        for (int i = 0; i < m; ++i){
            int a, b; cin >> a >> b;
            ed[a].push_back(b);
            ed[b].push_back(a);
        }
     
        string res;
        for (int i = 1; i <= n; ++i){
            int cursz = s[i];
            set<pair<int, int>> st;
            vector<bool> visited(n+1); visited[i] = true;
            for (auto to : ed[i]) st.insert({s[to], to});
            bool flag = true;
            while (!st.empty()){
                auto it = st.begin();
                if (it->first > cursz) {
                    flag = false;
                    break;
                }
                cursz += it->first;
                visited[it->second] = true;
                for (auto to : ed[it->second]) {
                    if (visited[to]) continue;
                    st.insert({s[to], to});
                };
                st.erase(it);
            }
     
            if (flag) res += '1';
            else res += '0';
        }
     
        cout << res << "\n";
     
        return 0;
    }

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 245 ms 420 KB Output is correct
5 Correct 231 ms 424 KB Output is correct
6 Correct 368 ms 416 KB Output is correct
7 Correct 241 ms 420 KB Output is correct
8 Correct 183 ms 404 KB Output is correct
9 Correct 326 ms 592 KB Output is correct
10 Correct 135 ms 420 KB Output is correct
11 Correct 127 ms 408 KB Output is correct
12 Correct 125 ms 436 KB Output is correct
13 Correct 221 ms 408 KB Output is correct
14 Correct 127 ms 428 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Execution timed out 1084 ms 15760 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1075 ms 12708 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1067 ms 14124 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 245 ms 420 KB Output is correct
5 Correct 231 ms 424 KB Output is correct
6 Correct 368 ms 416 KB Output is correct
7 Correct 241 ms 420 KB Output is correct
8 Correct 183 ms 404 KB Output is correct
9 Correct 326 ms 592 KB Output is correct
10 Correct 135 ms 420 KB Output is correct
11 Correct 127 ms 408 KB Output is correct
12 Correct 125 ms 436 KB Output is correct
13 Correct 221 ms 408 KB Output is correct
14 Correct 127 ms 428 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Execution timed out 1084 ms 15760 KB Time limit exceeded
18 Halted 0 ms 0 KB -