oj.uz

답안 #573241

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
573241 2022-06-06T09:46:56 Z MohamedFaresNebili Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 14612 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

        using namespace std;
        using namespace __gnu_pbds;

        using ll = long long;
        using ii = pair<int, int>;
        using vi = vector<int>;

        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second
        #define lb lower_bound
        #define int ll

        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;

        int N, M, S[200001];
        vector<int> adj[200001];
        void subtask2() {
            string res(N, '0');
            for(int l = 1; l <= N; l++) {
                if(S[l] != S[1]) continue;
                res[l - 1] = '1';
            }
            cout << res << "\n";
        }

        int32_t main() {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            cin >> N >> M; int R = 0; string res(N, '0');
            for(int l = 1; l <= N; l++)
                cin >> S[l], R += S[l];
            for(int l = 0; l < M; l++) {
                int U, V; cin >> U >> V;
                adj[U].pb(V); adj[V].pb(U);
            }
            bool ok = (adj[1].size() == N - 1);
            for(int l = 2; l <= N; l++) {
                ok &= (adj[l].size() == 1);
                int U = adj[l][0];
                ok &= (U == 1); ok &= (S[l] <= S[l - 1]);
            }
            if(ok) {
                subtask2();
                return 0;
            }
            for(int l = 1; l <= N; l++) {
                int curr = 0;
                priority_queue<ii, vector<ii>, greater<ii>> pq;
                pq.push({0, l}); vector<bool> vis(N + 1, 0);
                while(!pq.empty()) {
                    int A = pq.top().second, B = pq.top().first; pq.pop();
                    if(vis[A] || (S[A] > curr && A != l)) continue;
                    vis[A] = 1; curr += S[A];
                    for(auto E : adj[A]) {
                        if(vis[E]) continue;
                        pq.push({S[E], E});
                    }
                }
                if(curr == R) res[l - 1] = '1';
            }
            cout << res << "\n";
        }

Compilation message

island.cpp: In function 'int32_t main()':
island.cpp:41:38: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   41 |             bool ok = (adj[1].size() == N - 1);
      |                        ~~~~~~~~~~~~~~^~~~~~~~
island.cpp:56:46: warning: unused variable 'B' [-Wunused-variable]
   56 |                     int A = pq.top().second, B = pq.top().first; pq.pop();
      |                                              ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 196 ms 5100 KB Output is correct
5 Correct 160 ms 5100 KB Output is correct
6 Correct 268 ms 5116 KB Output is correct
7 Correct 195 ms 5104 KB Output is correct
8 Correct 151 ms 5096 KB Output is correct
9 Correct 242 ms 5120 KB Output is correct
10 Correct 63 ms 5084 KB Output is correct
11 Correct 60 ms 5088 KB Output is correct
12 Correct 59 ms 5120 KB Output is correct
13 Correct 108 ms 5092 KB Output is correct
14 Correct 89 ms 5076 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4984 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Execution timed out 1093 ms 14612 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 1090 ms 12904 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 1092 ms 14092 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 196 ms 5100 KB Output is correct
5 Correct 160 ms 5100 KB Output is correct
6 Correct 268 ms 5116 KB Output is correct
7 Correct 195 ms 5104 KB Output is correct
8 Correct 151 ms 5096 KB Output is correct
9 Correct 242 ms 5120 KB Output is correct
10 Correct 63 ms 5084 KB Output is correct
11 Correct 60 ms 5088 KB Output is correct
12 Correct 59 ms 5120 KB Output is correct
13 Correct 108 ms 5092 KB Output is correct
14 Correct 89 ms 5076 KB Output is correct
15 Correct 3 ms 4984 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Execution timed out 1093 ms 14612 KB Time limit exceeded
18 Halted 0 ms 0 KB -