oj.uz

Submission #1078942

# Submission time Handle Problem Language Result Execution time Memory
1078942 2024-08-28T08:26:27 Z LIF Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 524288 KB 
#include<bits/stdc++.h>
using namespace std;
int n,m;
int head[500005];
int cnt = 0;
long long int a[500005];
int last[500005];
long long int siz[500005];
struct edg
{
    int to;
    int next;
}edge[500005];
void add(int x,int y)
{
    cnt++;
    edge[cnt].to = y;
    edge[cnt].next = head[x];
    head[x] = cnt;
}
void dfs(int now,int fa)
{
    siz[now] = a[now];
    for(int i=head[now];i!=0;i=edge[i].next)
    {
        int to = edge[i].to;
        if(to == fa)continue;
        dfs(to,now);
        siz[now] += siz[to];
    }
    return;
}
void dfs2(int now,int fa)
{
    if(siz[now] >= a[fa] && last[fa] == 1)last[now] = 1;
    for(int i=head[now];i!=0;i=edge[i].next)
    {
        int to = edge[i].to;
        if(to == fa)continue;
        dfs2(to,now);
    }
    return;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    dfs(1,0);
    last[0] = 1;
    dfs2(1,0);
    for(int i=1;i<=n;i++)cout<<last[i];
    cout<<endl;




    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 297 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 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 151 ms 19024 KB Output is correct
4 Correct 141 ms 16996 KB Output is correct
5 Correct 133 ms 12368 KB Output is correct
6 Correct 139 ms 12560 KB Output is correct
7 Correct 135 ms 12624 KB Output is correct
8 Correct 156 ms 12756 KB Output is correct
9 Correct 126 ms 12368 KB Output is correct
10 Correct 105 ms 11116 KB Output is correct
11 Correct 102 ms 11856 KB Output is correct
12 Correct 114 ms 10832 KB Output is correct
13 Correct 113 ms 26192 KB Output is correct
14 Correct 125 ms 26448 KB Output is correct
15 Correct 139 ms 28500 KB Output is correct
16 Correct 125 ms 27728 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 148 ms 28328 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 348 KB Output is correct
2 Execution timed out 1102 ms 401776 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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