oj.uz

Submission #714792

# Submission time Handle Problem Language Result Execution time Memory
714792 2023-03-25T09:26:53 Z Toxtaq Stranded Far From Home (BOI22_island) C++17
20 / 100
 1000 ms 290088 KB 
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>>g;
vector<int>num;
vector<long long>cnt1;
vector<int>canTraverse; /// 0-unchecked, 1-false, 2-true
void calc(int u, int par){
    cnt1[u] = num[u];
    for(int v : g[u]){
        if(v != par){
            calc(v, u);
            cnt1[u] += cnt1[v];
        }
    }
}
void dfs1(int u, int par){
    if(canTraverse[par] == 1)canTraverse[u] = 1;
    else{
        canTraverse[u] = (cnt1[u] >= num[par]) + 1;
    }
    for(int v : g[u]){
        if(v != par){
            dfs1(v, u);
        }
    }
}
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;
    if(n <= 2000 && m <= 2000){
        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;
    }
    else{
        g.resize(n + 1);
        num.resize(n + 1);
        cnt1.resize(n + 1);
        canTraverse.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);
        }
        calc(1, 1);
        dfs1(1, 1);
        for(int i = 1;i <= n;++i){
            if(canTraverse[i] == 2)cout << 1;
            else cout << 0;
        }
    }

}

Compilation message

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

Subtask #1
10.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 Correct 0 ms 212 KB Output is correct
4 Correct 128 ms 432 KB Output is correct
5 Correct 138 ms 408 KB Output is correct
6 Correct 148 ms 420 KB Output is correct
7 Correct 122 ms 452 KB Output is correct
8 Correct 86 ms 420 KB Output is correct
9 Correct 167 ms 524 KB Output is correct
10 Correct 129 ms 640 KB Output is correct
11 Correct 142 ms 644 KB Output is correct
12 Correct 92 ms 396 KB Output is correct
13 Correct 210 ms 632 KB Output is correct
14 Correct 75 ms 404 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 300 ms 19548 KB Output is correct
4 Correct 241 ms 19528 KB Output is correct
5 Correct 299 ms 14264 KB Output is correct
6 Correct 345 ms 14540 KB Output is correct
7 Correct 300 ms 14600 KB Output is correct
8 Correct 331 ms 14660 KB Output is correct
9 Correct 316 ms 14516 KB Output is correct
10 Correct 251 ms 15336 KB Output is correct
11 Correct 215 ms 15280 KB Output is correct
12 Correct 283 ms 14704 KB Output is correct
13 Correct 238 ms 27028 KB Output is correct
14 Correct 239 ms 27072 KB Output is correct
15 Correct 302 ms 27072 KB Output is correct
16 Correct 201 ms 26744 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 300 ms 26908 KB Output isn't correct
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 1096 ms 290088 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.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 Correct 0 ms 212 KB Output is correct
4 Correct 128 ms 432 KB Output is correct
5 Correct 138 ms 408 KB Output is correct
6 Correct 148 ms 420 KB Output is correct
7 Correct 122 ms 452 KB Output is correct
8 Correct 86 ms 420 KB Output is correct
9 Correct 167 ms 524 KB Output is correct
10 Correct 129 ms 640 KB Output is correct
11 Correct 142 ms 644 KB Output is correct
12 Correct 92 ms 396 KB Output is correct
13 Correct 210 ms 632 KB Output is correct
14 Correct 75 ms 404 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 300 ms 19548 KB Output is correct
18 Correct 241 ms 19528 KB Output is correct
19 Correct 299 ms 14264 KB Output is correct
20 Correct 345 ms 14540 KB Output is correct
21 Correct 300 ms 14600 KB Output is correct
22 Correct 331 ms 14660 KB Output is correct
23 Correct 316 ms 14516 KB Output is correct
24 Correct 251 ms 15336 KB Output is correct
25 Correct 215 ms 15280 KB Output is correct
26 Correct 283 ms 14704 KB Output is correct
27 Correct 238 ms 27028 KB Output is correct
28 Correct 239 ms 27072 KB Output is correct
29 Correct 302 ms 27072 KB Output is correct
30 Correct 201 ms 26744 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Incorrect 300 ms 26908 KB Output isn't correct
33 Halted 0 ms 0 KB -