oj.uz

Submission #968319

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

const int MX=2e5+10;
vector < int > mas[MX];
long long s[MX],sum[MX],prd[MX],ans[MX];
int n,m;

void DFS(int zar,int mun)
{
    sum[zar]=s[zar];
    prd[zar]=mun;
    for(auto u:mas[zar])
    {
        if(u!=mun)
        {
            DFS(u,zar);
            sum[zar]+=sum[u];
        }
    }
}

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);
    }

    DFS(1,0);

    ans[0]=1;
    for(int i=1;i<=n;i++)
    {
        if(sum[i]>=s[prd[i]] && ans[prd[i]])
        {
            ans[i]=1;
        }
    }

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

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 373 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11100 KB Output is correct
2 Correct 2 ms 11228 KB Output is correct
3 Correct 94 ms 28240 KB Output is correct
4 Correct 86 ms 26968 KB Output is correct
5 Correct 92 ms 21840 KB Output is correct
6 Correct 96 ms 22312 KB Output is correct
7 Correct 111 ms 22352 KB Output is correct
8 Correct 101 ms 22360 KB Output is correct
9 Correct 80 ms 22100 KB Output is correct
10 Correct 69 ms 21960 KB Output is correct
11 Correct 62 ms 21952 KB Output is correct
12 Correct 98 ms 21276 KB Output is correct
13 Correct 83 ms 36176 KB Output is correct
14 Correct 107 ms 36436 KB Output is correct
15 Correct 93 ms 37780 KB Output is correct
16 Correct 69 ms 37016 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11096 KB Output is correct
2 Incorrect 92 ms 37152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 373 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -