oj.uz

답안 #750591

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
750591 2023-05-29T19:54:05 Z Rasoul006 Stranded Far From Home (BOI22_island) C++17
0 / 100
 152 ms 36416 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 += '1' , 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}) ;
    }

    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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 23704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23752 KB Output is correct
2 Incorrect 137 ms 36208 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Incorrect 152 ms 36416 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -