Submission #968319

#	Time	Username	Problem	Language	Result	Execution time	Memory
968319		maxFedorchuk	Stranded Far From Home (BOI22_island)	C++17	10 / 100	1052 ms	524288 KiB

island

#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
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35