oj.uz

Submission #750597

# Submission time Handle Problem Language Result Execution time Memory
750597 2023-05-29T20:01:58 Z Rasoul006 Stranded Far From Home (BOI22_island) C++17
0 / 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] ;

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

}

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

    cin >> n >> m ;

    string s = "" ;

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

    s[0] = '1' ;

    for (int i = 2 ; i<=n ; i++)
        s[i-1] = (a[pa[i]] <= sz[i] ? '1' : '0') ;


    cout << s << endl ;

    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 14 ms 23812 KB Output is correct
3 Correct 162 ms 42992 KB Output is correct
4 Incorrect 148 ms 44156 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Incorrect 153 ms 49336 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 23752 KB Output is correct
2 Execution timed out 1058 ms 257388 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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