oj.uz

Submission #714794

# Submission time Handle Problem Language Result Execution time Memory
714794 2023-03-25T09:37:12 Z Toxtaq Stranded Far From Home (BOI22_island) C++17
20 / 100
 1000 ms 306612 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;
    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;
    num.resize(n + 1);
    g.resize(n + 1);
    vis.resize(n + 1);
    chosen.resize(n + 1);
    cnt1.resize(n + 1);
    canTraverse.resize(n + 1);
    for(int i = 1;i <= n;++i)cin >> num[i];
    bool check = 1;
    for(int i = 0;i < m;++i){
        int u, v;
        cin >> u >> v;
        if(abs(u - v) > 1)check = 0;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    if(n <= 2000 && m <= 2000){
        for(int i = 1;i <= n;++i){
            sort(g[i].begin(), g[i].end(), cmp);
        }
        string s = "";
        for(int i = 1;i <= n;++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];
                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;
            }
            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 if(check){
        int root = -1, mx = 0;
        for(int i = 1;i <= n;++i){
            if(mx < num[i]){
                mx = num[i];
                root = i;
            }
        }
        calc(root, root);
        dfs1(root, root);
        for(int i = 1;i <= n;++i){
            if(canTraverse[i] == 2)cout << 1;
            else cout << 0;
        }
    }
    else{
        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:82:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             while(tmp.size() && ind < 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 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 114 ms 468 KB Output is correct
5 Correct 128 ms 440 KB Output is correct
6 Correct 148 ms 444 KB Output is correct
7 Correct 108 ms 452 KB Output is correct
8 Correct 80 ms 436 KB Output is correct
9 Correct 153 ms 548 KB Output is correct
10 Correct 128 ms 660 KB Output is correct
11 Correct 125 ms 660 KB Output is correct
12 Correct 110 ms 436 KB Output is correct
13 Correct 220 ms 596 KB Output is correct
14 Correct 72 ms 444 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 283 ms 19688 KB Output is correct
4 Correct 258 ms 19696 KB Output is correct
5 Correct 329 ms 14284 KB Output is correct
6 Correct 303 ms 14672 KB Output is correct
7 Correct 312 ms 14836 KB Output is correct
8 Correct 337 ms 14792 KB Output is correct
9 Correct 306 ms 14572 KB Output is correct
10 Correct 218 ms 15452 KB Output is correct
11 Correct 207 ms 15332 KB Output is correct
12 Correct 262 ms 14712 KB Output is correct
13 Correct 243 ms 27252 KB Output is correct
14 Correct 240 ms 27148 KB Output is correct
15 Correct 263 ms 27112 KB Output is correct
16 Correct 196 ms 26844 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 280 ms 21324 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 1087 ms 306612 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 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 114 ms 468 KB Output is correct
5 Correct 128 ms 440 KB Output is correct
6 Correct 148 ms 444 KB Output is correct
7 Correct 108 ms 452 KB Output is correct
8 Correct 80 ms 436 KB Output is correct
9 Correct 153 ms 548 KB Output is correct
10 Correct 128 ms 660 KB Output is correct
11 Correct 125 ms 660 KB Output is correct
12 Correct 110 ms 436 KB Output is correct
13 Correct 220 ms 596 KB Output is correct
14 Correct 72 ms 444 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 283 ms 19688 KB Output is correct
18 Correct 258 ms 19696 KB Output is correct
19 Correct 329 ms 14284 KB Output is correct
20 Correct 303 ms 14672 KB Output is correct
21 Correct 312 ms 14836 KB Output is correct
22 Correct 337 ms 14792 KB Output is correct
23 Correct 306 ms 14572 KB Output is correct
24 Correct 218 ms 15452 KB Output is correct
25 Correct 207 ms 15332 KB Output is correct
26 Correct 262 ms 14712 KB Output is correct
27 Correct 243 ms 27252 KB Output is correct
28 Correct 240 ms 27148 KB Output is correct
29 Correct 263 ms 27112 KB Output is correct
30 Correct 196 ms 26844 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Incorrect 280 ms 21324 KB Output isn't correct
33 Halted 0 ms 0 KB -