oj.uz

Submission #968303

# Submission time Handle Problem Language Result Execution time Memory
968303 2024-04-23T09:51:37 Z maxFedorchuk Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 19444 KB 
#include <bits/stdc++.h>
using namespace std;

const int MX=2e5+10;
vector < int > mas[MX];
int s[MX],use[MX];
int n,m;

bool chk(int vr)
{
    fill(use+1,use+1+n,0);

    priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > q;
    for(auto u:mas[vr])
    {
        q.push({s[u],u});
    }

    long long sum=s[vr],k1=1;
    use[vr]=1;
    while(!q.empty())
    {
        int zar=q.top().second;
        q.pop();

        if(use[zar])
        {
            continue;
        }

        use[zar]=1;
        k1++;

        if(s[zar]>sum)
        {
            return 0;
        }
        sum+=s[zar];

        for(auto u:mas[zar])
        {
            q.push({s[u],u});
        }
    }

    return (k1==n);
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
    }

    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;

        mas[a].push_back(b);
        mas[b].push_back(a);
    }

    for(int i=1;i<=n;i++)
    {
        cout<<chk(i);
    }
    cout<<"\n";

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 292 ms 6740 KB Output is correct
5 Correct 227 ms 6492 KB Output is correct
6 Correct 381 ms 6736 KB Output is correct
7 Correct 291 ms 6492 KB Output is correct
8 Correct 222 ms 6492 KB Output is correct
9 Correct 321 ms 6648 KB Output is correct
10 Correct 108 ms 6492 KB Output is correct
11 Correct 101 ms 6488 KB Output is correct
12 Correct 98 ms 6624 KB Output is correct
13 Correct 296 ms 6648 KB Output is correct
14 Correct 144 ms 6616 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6792 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Execution timed out 1072 ms 19444 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Execution timed out 1083 ms 17296 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 6488 KB Output is correct
2 Execution timed out 1030 ms 17528 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 292 ms 6740 KB Output is correct
5 Correct 227 ms 6492 KB Output is correct
6 Correct 381 ms 6736 KB Output is correct
7 Correct 291 ms 6492 KB Output is correct
8 Correct 222 ms 6492 KB Output is correct
9 Correct 321 ms 6648 KB Output is correct
10 Correct 108 ms 6492 KB Output is correct
11 Correct 101 ms 6488 KB Output is correct
12 Correct 98 ms 6624 KB Output is correct
13 Correct 296 ms 6648 KB Output is correct
14 Correct 144 ms 6616 KB Output is correct
15 Correct 3 ms 6792 KB Output is correct
16 Correct 2 ms 6492 KB Output is correct
17 Execution timed out 1072 ms 19444 KB Time limit exceeded
18 Halted 0 ms 0 KB -