oj.uz

Submission #917746

# Submission time Handle Problem Language Result Execution time Memory
917746 2024-01-28T17:11:23 Z themm1 Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 16140 KB 
#include <bits/stdc++.h>
using namespace std;
// ordered set whith s.order_of_key(x) method, which returns rank of element x in set s
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
*/

// pair printing
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "(" << par.first << "; " << par.second << ")"; return out;}
// set printing
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for(const auto &x:cont) out << x << ", "; out << "}"; return out; }
// map printing
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for(const auto &x:cont) out << x << ", "; out << "}"; return out; }
// unordered_set printing
template <class T>
ostream& operator<<(ostream& out, const unordered_set<T> &cont) {out << "{";for(const auto &x:cont) out << x << ", ";out << "}";return out;}
// unordered_map printing
template <class T, class U>
ostream& operator<<(ostream& out, const unordered_map<T, U> &cont) {out << "{";for(const auto &x:cont) out << x << ", ";out << "}";return out;}
// vector printing
template<class T>
ostream& operator<<(ostream& out, const vector<T> &cont){ out << "[";  for (const auto &x:cont) out << x << ", ";  out << "]"; return out;}

#define print(x) cout << (x) << endl;
#define dmp(x) cerr << #x << " = " << x << endl
#define dmpn(x) cerr << #x << " = " << x << "; "
#define dmpl(x) cerr << "Line " << __LINE__ << ": " << #x << " = " << x << endl

#define int long long
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define pb push_back
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define contains(s,x) ((s).find(x) != (s).end())
const int MOD = 998244353;

int N, M;
vector<vector<int>> g;
vector<int> values;

void solve() {
        cin >> N >> M;
        g.assign(N, {});
        values.assign(N, 0);
        for (int i = 0; i < N; i++) cin >> values[i];
        for (int i = 0; i < M; i++) {
                int u, v;
                cin >> u >> v;
                u--;
                v--;
                g[u].pb(v);
                g[v].pb(u);
        }

        vector<bool> answer(N, 0);
        for (int i = 0; i < N; i++) {
                set<pii> s = { {values[i], i} };
                int sum = values[i];
                vector<bool> visited(N, 0);
                while (!s.empty()) {
                        pii pr = (*s.begin());
                        if (pr.ff > sum) break;
                        s.erase(pr);
                        int v = pr.ss;
                        if (v != i) sum += pr.ff;
                        visited[v] = 1;
                        for (int u : g[v]) if (!visited[u]) {
                                s.insert({ values[u], u });
                        }
                }
                if (s.empty()) answer[i] = 1;
        }
        for (int x : answer) cout << x;
        cout << endl;
}

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

        int t = 1;
        // cin >> t;
        while (t--) {
                solve();
        }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 231 ms 580 KB Output is correct
5 Correct 222 ms 616 KB Output is correct
6 Correct 355 ms 604 KB Output is correct
7 Correct 238 ms 616 KB Output is correct
8 Correct 172 ms 604 KB Output is correct
9 Correct 318 ms 664 KB Output is correct
10 Correct 99 ms 604 KB Output is correct
11 Correct 101 ms 604 KB Output is correct
12 Correct 110 ms 856 KB Output is correct
13 Correct 206 ms 580 KB Output is correct
14 Correct 119 ms 604 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 1060 ms 16140 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 1088 ms 12832 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 1051 ms 14320 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 231 ms 580 KB Output is correct
5 Correct 222 ms 616 KB Output is correct
6 Correct 355 ms 604 KB Output is correct
7 Correct 238 ms 616 KB Output is correct
8 Correct 172 ms 604 KB Output is correct
9 Correct 318 ms 664 KB Output is correct
10 Correct 99 ms 604 KB Output is correct
11 Correct 101 ms 604 KB Output is correct
12 Correct 110 ms 856 KB Output is correct
13 Correct 206 ms 580 KB Output is correct
14 Correct 119 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Execution timed out 1060 ms 16140 KB Time limit exceeded
18 Halted 0 ms 0 KB -