oj.uz

Submission #714695

# Submission time Handle Problem Language Result Execution time Memory
714695 2023-03-25T08:02:32 Z Toxtaq Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 36784 KB 
#include <bits/stdc++.h>
using namespace std;
/*
7 6
4 2 20 6 8 2 22
1 2
2 3
3 6
1 4
4 5
5 7
*/
vector<vector<int>>g;
vector<int>num;
vector<bool>vis, chosen;
bool cmp(int a, int b){
    return num[a] < num[b];
}
long long cnt = 0;
vector<int>tmp;
void dfs(int u){
    vis[u] = 1;
//    cout << u << " ";
    vector<int>tempo;
    for(int v : g[u]){
        if(!chosen[v] && cnt >= num[v]){
            cnt += num[v];
            chosen[v] = 1;
            tempo.push_back(v);
        }
        else if(cnt < num[v]){
            tmp.push_back(v);
        }
    }
    for(int v : tempo){
        if(!vis[v]){
            dfs(v);
        }
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
    g.resize(n + 1);
    num.resize(n + 1);
    vis.resize(n + 1);
    chosen.resize(n + 1);
    for(int i = 1;i <= n;++i)cin >> num[i];
    for(int i = 0;i < m;++i){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 1;i <= n;++i){
        sort(g[i].begin(), g[i].end(), cmp);
    }
//    for(int i = 1;i <= n;++i){
//        cout << i << ": ";
//        for(int j : g[i]){
//            cout << j << " ";
//        }
//        cout << '\n';
//    }
    string s = "";
    for(int i = 1;i <= n;++i){
//        cout << i << ": ";
        cnt = num[i];
        chosen[i] = 1;
        dfs(i);
        sort(tmp.begin(), tmp.end(), cmp);
        int ind = 0;
        while(tmp.size() && ind < tmp.size()){
            int j = tmp[ind], sz = tmp.size();
            if(!chosen[j] && cnt >= num[j]){
                chosen[j] = 1;
                cnt += num[j];
                dfs(j);
            }
            else{
                ind++;
                continue;
            }
            sort(tmp.begin(), tmp.end(), cmp);
            ind = 0;
        }
//        cout << "CNT: " << cnt << '\n';
        bool ok = 1;
        for(int j = 1;j <= n && ok;++j){
            if(!vis[j]){
                ok = 0;
            }
        }
        for(int j = 1;j <= n;++j){
            vis[j] = 0;
            chosen[j] = 0;
        }
        if(ok)s += '1';
        else s += '0';
        tmp.clear();
    }
    cout << s;
}

Compilation message

island.cpp: In function 'int main()':
island.cpp:74:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         while(tmp.size() && ind < tmp.size()){
      |                             ~~~~^~~~~~~~~~~~
island.cpp:75:31: warning: unused variable 'sz' [-Wunused-variable]
   75 |             int j = tmp[ind], sz = tmp.size();
      |                               ^~

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 128 ms 428 KB Output is correct
5 Correct 140 ms 404 KB Output is correct
6 Correct 153 ms 420 KB Output is correct
7 Correct 112 ms 436 KB Output is correct
8 Correct 83 ms 420 KB Output is correct
9 Correct 156 ms 468 KB Output is correct
10 Correct 131 ms 640 KB Output is correct
11 Correct 123 ms 640 KB Output is correct
12 Correct 96 ms 340 KB Output is correct
13 Correct 206 ms 636 KB Output is correct
14 Correct 79 ms 340 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 244 KB Output is correct
3 Execution timed out 1087 ms 22084 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 1068 ms 36784 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 1064 ms 13856 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 128 ms 428 KB Output is correct
5 Correct 140 ms 404 KB Output is correct
6 Correct 153 ms 420 KB Output is correct
7 Correct 112 ms 436 KB Output is correct
8 Correct 83 ms 420 KB Output is correct
9 Correct 156 ms 468 KB Output is correct
10 Correct 131 ms 640 KB Output is correct
11 Correct 123 ms 640 KB Output is correct
12 Correct 96 ms 340 KB Output is correct
13 Correct 206 ms 636 KB Output is correct
14 Correct 79 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 244 KB Output is correct
17 Execution timed out 1087 ms 22084 KB Time limit exceeded
18 Halted 0 ms 0 KB -