oj.uz

답안 #877576

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
877576 2023-11-23T10:41:07 Z vjudge1 Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 13592 KB 
#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;
const double eps = 1e-9;

void setIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int32_t main() {
    setIO();

    int n, m;
    cin >> n >> m;
    vector<int> val(n+1);
    for(int i=1; i<=n; i++) cin >> val[i];

    vector<vector<int> > graph(n+1);
    for(int i=0; i<m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    auto dijkstra = [&](int a) {
        //cout << a << ": \n";
        int cnt = 0;
        ll total = 0;
        vector<bool> vis(n+1);
        priority_queue<pll, vector<pll>, greater<pll> > pq;
        pq.push({ 0, a });

        while(!pq.empty()) {
            int u = pq.top().second;
            pq.pop();

            //cout << u << '\n';

            if(vis[u] || (total < val[u] && u != a)) continue;
            vis[u] = true;
            total += val[u];
            cnt++;

            for(int &v : graph[u]) {
                if(vis[v]) continue;
                pq.push({ val[v], v });
            }
        }

        return (cnt == n);
    };

    for(int i=1; i<=n; i++)
        cout << dijkstra(i);
    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 177 ms 552 KB Output is correct
5 Correct 134 ms 856 KB Output is correct
6 Correct 229 ms 600 KB Output is correct
7 Correct 183 ms 576 KB Output is correct
8 Correct 142 ms 564 KB Output is correct
9 Correct 199 ms 604 KB Output is correct
10 Correct 51 ms 604 KB Output is correct
11 Correct 48 ms 604 KB Output is correct
12 Correct 43 ms 600 KB Output is correct
13 Correct 90 ms 344 KB Output is correct
14 Correct 78 ms 348 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 177 ms 552 KB Output is correct
5 Correct 134 ms 856 KB Output is correct
6 Correct 229 ms 600 KB Output is correct
7 Correct 183 ms 576 KB Output is correct
8 Correct 142 ms 564 KB Output is correct
9 Correct 199 ms 604 KB Output is correct
10 Correct 51 ms 604 KB Output is correct
11 Correct 48 ms 604 KB Output is correct
12 Correct 43 ms 600 KB Output is correct
13 Correct 90 ms 344 KB Output is correct
14 Correct 78 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Execution timed out 1037 ms 13592 KB Time limit exceeded
18 Halted 0 ms 0 KB -