oj.uz

Submission #750590

# Submission time Handle Problem Language Result Execution time Memory
750590 2023-05-29T19:50:11 Z Rasoul006 Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 41068 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 , mx ;

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 ;

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

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

        if (tot >= mx) {tot = all ; break; }

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

    st.clear() ;

    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 ;

        vis[u] = false ;

        for (auto it : g[u])
        {
            if (vis[it.S])
                st.insert(it) ;
            vis[it.S] = 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] , mx = max(mx , 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;
}

Compilation message

island.cpp: In function 'bool bfs(ll)':
island.cpp:96:22: warning: unused variable 'val' [-Wunused-variable]
   96 |         ll u = p.S , val = p.F ;
      |                      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 12 ms 23820 KB Output is correct
4 Correct 14 ms 23900 KB Output is correct
5 Correct 15 ms 23960 KB Output is correct
6 Correct 14 ms 23892 KB Output is correct
7 Correct 15 ms 23956 KB Output is correct
8 Correct 15 ms 23892 KB Output is correct
9 Correct 658 ms 23988 KB Output is correct
10 Correct 13 ms 23952 KB Output is correct
11 Correct 16 ms 23948 KB Output is correct
12 Correct 14 ms 23932 KB Output is correct
13 Correct 380 ms 23964 KB Output is correct
14 Correct 223 ms 23952 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23792 KB Output is correct
2 Correct 13 ms 23816 KB Output is correct
3 Correct 395 ms 41068 KB Output is correct
4 Execution timed out 1079 ms 39520 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23796 KB Output is correct
2 Correct 201 ms 40708 KB Output is correct
3 Correct 211 ms 40812 KB Output is correct
4 Correct 160 ms 40768 KB Output is correct
5 Execution timed out 1083 ms 39060 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 307 ms 40956 KB Output is correct
3 Correct 372 ms 40832 KB Output is correct
4 Correct 292 ms 40948 KB Output is correct
5 Correct 176 ms 40968 KB Output is correct
6 Correct 171 ms 40500 KB Output is correct
7 Execution timed out 1084 ms 39524 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 12 ms 23820 KB Output is correct
4 Correct 14 ms 23900 KB Output is correct
5 Correct 15 ms 23960 KB Output is correct
6 Correct 14 ms 23892 KB Output is correct
7 Correct 15 ms 23956 KB Output is correct
8 Correct 15 ms 23892 KB Output is correct
9 Correct 658 ms 23988 KB Output is correct
10 Correct 13 ms 23952 KB Output is correct
11 Correct 16 ms 23948 KB Output is correct
12 Correct 14 ms 23932 KB Output is correct
13 Correct 380 ms 23964 KB Output is correct
14 Correct 223 ms 23952 KB Output is correct
15 Correct 12 ms 23792 KB Output is correct
16 Correct 13 ms 23816 KB Output is correct
17 Correct 395 ms 41068 KB Output is correct
18 Execution timed out 1079 ms 39520 KB Time limit exceeded
19 Halted 0 ms 0 KB -