oj.uz

Submission #714638

# Submission time Handle Problem Language Result Execution time Memory
714638 2023-03-25T07:01:16 Z ismayil Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 16540 KB 
#include <bits/stdc++.h>
#define int long long
//#define endl '\n'
using namespace std;
const int MAX = 2e5 + 5;
vector<int> adj[MAX];
int color[MAX], sum[MAX];
int s[MAX], ans[MAX];
bool bfs(int st){
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push(make_pair(s[st], st));
    while (!q.empty())
    {
        int u = q.top().second;
        int w = q.top().first;
        q.pop();
        color[u] = 1;
        if(w > sum[st] && st != u) return false;
        sum[st] += w;
        for(auto v : adj[u]){
            if(!color[v]) q.push({s[v], v});
        }
        
    }
    return true;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m;
    cin>>n>>m;
    for(int i = 1; i <= n; i++) cin>>s[i];
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i = 1; i <= n; i++){
        memset(color, 0, sizeof(color));
        cout<<bfs(i);
    }
    cout<<endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 278 ms 6696 KB Output is correct
5 Correct 241 ms 6612 KB Output is correct
6 Correct 389 ms 6828 KB Output is correct
7 Correct 297 ms 6832 KB Output is correct
8 Correct 244 ms 6824 KB Output is correct
9 Correct 286 ms 6732 KB Output is correct
10 Correct 152 ms 6664 KB Output is correct
11 Correct 150 ms 6684 KB Output is correct
12 Correct 135 ms 6704 KB Output is correct
13 Correct 180 ms 6672 KB Output is correct
14 Correct 187 ms 6732 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 278 ms 6696 KB Output is correct
5 Correct 241 ms 6612 KB Output is correct
6 Correct 389 ms 6828 KB Output is correct
7 Correct 297 ms 6832 KB Output is correct
8 Correct 244 ms 6824 KB Output is correct
9 Correct 286 ms 6732 KB Output is correct
10 Correct 152 ms 6664 KB Output is correct
11 Correct 150 ms 6684 KB Output is correct
12 Correct 135 ms 6704 KB Output is correct
13 Correct 180 ms 6672 KB Output is correct
14 Correct 187 ms 6732 KB Output is correct
15 Correct 3 ms 6484 KB Output is correct
16 Correct 4 ms 6484 KB Output is correct
17 Execution timed out 1085 ms 16540 KB Time limit exceeded
18 Halted 0 ms 0 KB -