oj.uz

Submission #750585

# Submission time Handle Problem Language Result Execution time Memory
750585 2023-05-29T18:58:02 Z Rasoul006 Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 42764 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] , all ;

vector <pair <ll,ll>> g[N] ;

set <pair <ll,ll>> st ;

bool vis[N] ;

bool bfs (ll i)
{
    ll tot = 0 ;

    st.insert ({a[i] , i}) ;

    while (!st.empty())
    {
        pair <ll,ll> p = *st.begin() ;
        st.erase(st.begin()) ;

        ll u = p.S , val = p.F ;
//
//        cout << u << " " << a[u] << " " << tot << endl ;

        if (tot < val && tot != 0) break ;

        tot += val ;
        vis[u] = true ;


        for (auto it : g[u])
        {
            if (!vis[it.S])
                st.insert(it) ;
            vis[it.S] = true ;
        }
    }

    st.clear();
    for (int i = 1 ; i<=n ; ++i)
        vis[i] = false ;

    return (tot == all) ;
}

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' , all += a[i] ;

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

    for (int i = 1 ; i<=n ; i++)
        s[i-1] = (bfs(i) ? '1' : '0') ;

    cout << s << endl ;

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23752 KB Output is correct
2 Correct 12 ms 23812 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 216 ms 23984 KB Output is correct
5 Correct 200 ms 23976 KB Output is correct
6 Correct 285 ms 23892 KB Output is correct
7 Correct 195 ms 24012 KB Output is correct
8 Correct 148 ms 23952 KB Output is correct
9 Correct 307 ms 24012 KB Output is correct
10 Correct 109 ms 23892 KB Output is correct
11 Correct 102 ms 23976 KB Output is correct
12 Correct 121 ms 23980 KB Output is correct
13 Correct 183 ms 23956 KB Output is correct
14 Correct 117 ms 23892 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23688 KB Output is correct
2 Correct 11 ms 23776 KB Output is correct
3 Execution timed out 1077 ms 42764 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23812 KB Output is correct
2 Execution timed out 1080 ms 41096 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23752 KB Output is correct
2 Correct 12 ms 23812 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 216 ms 23984 KB Output is correct
5 Correct 200 ms 23976 KB Output is correct
6 Correct 285 ms 23892 KB Output is correct
7 Correct 195 ms 24012 KB Output is correct
8 Correct 148 ms 23952 KB Output is correct
9 Correct 307 ms 24012 KB Output is correct
10 Correct 109 ms 23892 KB Output is correct
11 Correct 102 ms 23976 KB Output is correct
12 Correct 121 ms 23980 KB Output is correct
13 Correct 183 ms 23956 KB Output is correct
14 Correct 117 ms 23892 KB Output is correct
15 Correct 13 ms 23688 KB Output is correct
16 Correct 11 ms 23776 KB Output is correct
17 Execution timed out 1077 ms 42764 KB Time limit exceeded
18 Halted 0 ms 0 KB -