oj.uz

답안 #714965

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
714965 2023-03-25T15:35:11 Z aykhn Stranded Far From Home (BOI22_island) C++14
10 / 100
 342 ms 25252 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define OPT ios_base::sync_with_stdio(0); \
            cin.tie(0); \
            cout.tie(0)

#define pii pair<int,int>
#define pll pair<ll,ll>
#define endl "\n"
#define all(v) v.begin(), v.end()
#define mpr make_pair
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define inf 0x3F3F3F3F
#define bpc __builtin_popcount
#define print(v) for(int i = 0; i < v.size(); i++) \
                    cout << v[i] << " "; \
                    cout<<endl;

/*
int ternarySearch(int l, int r, int key, int ar[])
{
    if (r >= l)
    {
        int mid1 = l + (r - l) / 3;
        int mid2 = r - (r - l) / 3;

        if (ar[mid1] == key) {
            return mid1;
        }
        if (ar[mid2] == key) {
            return mid2;
        }
        if (key < ar[mid1]) {
            return ternarySearch(l, mid1 - 1, key, ar);
        }
        else if (key > ar[mid2]) {
            return ternarySearch(mid2 + 1, r, key, ar);
        }
        else {
            return ternarySearch(mid1 + 1, mid2 - 1, key, ar);
        }
    }
    return -1;
}
*/
ll n;
vector<ll> v(200001);
vector<vector<ll>> adj(200001);

bool dijkstra(int a)
{
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, a});
    ll cnt = v[a];
    vector<bool> used(2001);
    bool flag = true;
    while (!pq.empty())
    {
        int w = pq.top().fi;
        int from = pq.top().se;
        used[from] = true;
        pq.pop();
        if (w <= cnt)
        {
            cnt += w;
            for (int i = 0; i < adj[from].size(); i++)
            {
                if (!used[adj[from][i]])
                {
                    pq.push({v[adj[from][i]], adj[from][i]});
                }
            }
        }
        else
        {
            flag = false;
            break;
        }
    }
    return flag;
}
vector<int> used;
vector<int> s;
vector<bool> ans;

int dfs1(int a)
{
    s[a] = v[a];
    used[a] = true;
    for (int i = 0; i < adj[a].size(); i++)
    {
        if (!used[adj[a][i]])
        {
            s[a] += dfs1(adj[a][i]);
        }
    }

    return s[a];
}
void dfs2(int a)
{
    ans[a] = 1;
    used[a] = true;

    for (int i = 0; i < adj[a].size(); i++)
    {
        if (s[adj[a][i]] >= v[a] && ans[a] && !used[adj[a][i]])
        {
            ans[adj[a][i]] = 1;
            dfs2(adj[a][i]);
        }
    }
}
int main()
{
    ll m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
    while (m--)
    {
        ll u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    if (n <= 2000 && m <= 2000)
    {
        for (int i = 1; i <= n; i++)
        {
            if (dijkstra(i)) cout << "1";
            else cout << "0";
        }
        return 0;
    }

    used.assign(n + 1, false);
    s.assign(n + 1, 0);
    ans.assign(n + 1, 0);

    dfs1(1);
    for (int i = 1; i <= n; i++) used[i] = false;
    ans[1] = 1;
    dfs2(1);

    for (int i = 1; i <= n; i++)
    {
        cout << ans[i];
    }

    cout << endl;
}

Compilation message

island.cpp: In function 'bool dijkstra(int)':
island.cpp:73:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             for (int i = 0; i < adj[from].size(); i++)
      |                             ~~^~~~~~~~~~~~~~~~~~
island.cpp: In function 'int dfs1(int)':
island.cpp:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for (int i = 0; i < adj[a].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
island.cpp: In function 'void dfs2(int)':
island.cpp:112:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for (int i = 0; i < adj[a].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct
3 Correct 4 ms 6584 KB Output is correct
4 Correct 231 ms 6668 KB Output is correct
5 Correct 159 ms 6672 KB Output is correct
6 Correct 342 ms 6672 KB Output is correct
7 Correct 243 ms 6676 KB Output is correct
8 Correct 188 ms 6612 KB Output is correct
9 Correct 229 ms 6584 KB Output is correct
10 Correct 72 ms 6664 KB Output is correct
11 Correct 70 ms 6612 KB Output is correct
12 Correct 72 ms 6612 KB Output is correct
13 Correct 132 ms 6652 KB Output is correct
14 Correct 105 ms 6656 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6568 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct
3 Incorrect 286 ms 20736 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Incorrect 307 ms 17764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct
3 Correct 4 ms 6584 KB Output is correct
4 Correct 231 ms 6668 KB Output is correct
5 Correct 159 ms 6672 KB Output is correct
6 Correct 342 ms 6672 KB Output is correct
7 Correct 243 ms 6676 KB Output is correct
8 Correct 188 ms 6612 KB Output is correct
9 Correct 229 ms 6584 KB Output is correct
10 Correct 72 ms 6664 KB Output is correct
11 Correct 70 ms 6612 KB Output is correct
12 Correct 72 ms 6612 KB Output is correct
13 Correct 132 ms 6652 KB Output is correct
14 Correct 105 ms 6656 KB Output is correct
15 Correct 4 ms 6568 KB Output is correct
16 Correct 4 ms 6484 KB Output is correct
17 Incorrect 286 ms 20736 KB Output isn't correct
18 Halted 0 ms 0 KB -