oj.uz

Submission #750598

# Submission time Handle Problem Language Result Execution time Memory
750598 2023-05-29T20:09:20 Z Rasoul006 Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 524288 KB 
#include <bits/stdc++.h>

#define endl "\n"

#define F first

#define S second

#define pb push_back

#define all(x) x.begin() , x.end()

#define mm(dp , val) memset (dp , val , sizeof dp)

#define mid ((r+l)>>1)

#define lx (n<<1)

#define rx ((n<<1)|1)

#define low (i&(-i))

#define lb lower_bound

#define ub upper_bound

#define no void (cout << "NO" << endl)

#define one void (cout << "-1" << endl)

#define zer void (cout << "0" << endl)

#define yes void (cout << "YES" << endl)

typedef long long ll;

using namespace std;

const int logn = 26 ;

const int N = 1e6+5;

const int mod = 1e9+7;

const long long oo = 4557430888798830399 ;

ll dx[] = {0 , 0 , 1 , -1};
ll dy[] = {1 , -1 , 0 , 0};

ll n , m , a[N] , pa[N] , sz[N] ;

vector <ll> g[N] ;

string s ;

void dfs (ll u , ll p)
{
    pa[u] = p ;

    sz[u] = a[u] ;

    for (auto it : g[u])
    {
        if (it == p) continue ;

        dfs(it , u) ;
        sz[u] += sz[it] ;
    }

}

void dfs2 (ll u , ll p)
{
    s[u-1] = '1' ;

    for (auto it : g[u])
    {
        if (sz[it] < a[u] || it == p) continue ;
        dfs2 (it , u) ;
    }
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin >> n >> m ;

    for (int i = 1 ; i<=n ; i++)
        cin >> a[i] , s += '0' ;

    for (int i = 0 ; i<m ; i++)
    {
        ll u , v ;
        cin >> u >> v ;
        g[u].pb(v) ;
        g[v].pb(u) ;
    }

    dfs (1 , 1) ;

    dfs2 (1 , 1) ;


    cout << s << endl ;

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 224 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 13 ms 23892 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 139 ms 41104 KB Output is correct
4 Correct 122 ms 41164 KB Output is correct
5 Correct 161 ms 40076 KB Output is correct
6 Correct 174 ms 40544 KB Output is correct
7 Correct 168 ms 40544 KB Output is correct
8 Correct 180 ms 40628 KB Output is correct
9 Correct 140 ms 41808 KB Output is correct
10 Correct 90 ms 40292 KB Output is correct
11 Correct 92 ms 40084 KB Output is correct
12 Correct 157 ms 39256 KB Output is correct
13 Correct 123 ms 50484 KB Output is correct
14 Correct 133 ms 50776 KB Output is correct
15 Correct 158 ms 52120 KB Output is correct
16 Correct 89 ms 51192 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Incorrect 173 ms 47592 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23764 KB Output is correct
2 Execution timed out 1091 ms 308780 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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