oj.uz

Submission #714889

# Submission time Handle Problem Language Result Execution time Memory
714889 2023-03-25T11:51:07 Z aykhn Stranded Far From Home (BOI22_island) C++14
10 / 100
 367 ms 980 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(2001);
vector<vector<ll>> adj(2001);

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)
{
    if (a == 1)
    {
        ans[a] = 1;
    }

    for (int i = 0; i < adj[a].size(); i++)
    {
        if (s[adj[a][i]] >= v[a] && ans[a])
        {
            ans[adj[a][i]] = 1;
            dfs2(adj[a][i]);
        }
        else
        {
            ans[adj[a][i]] = 0;
        }
    }
}
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);
    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:114:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for (int i = 0; i < adj[a].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 360 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 213 ms 468 KB Output is correct
5 Correct 149 ms 468 KB Output is correct
6 Correct 367 ms 468 KB Output is correct
7 Correct 222 ms 472 KB Output is correct
8 Correct 183 ms 448 KB Output is correct
9 Correct 204 ms 468 KB Output is correct
10 Correct 70 ms 440 KB Output is correct
11 Correct 67 ms 448 KB Output is correct
12 Correct 62 ms 392 KB Output is correct
13 Correct 120 ms 444 KB Output is correct
14 Correct 92 ms 340 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Runtime error 10 ms 852 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Runtime error 11 ms 892 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Runtime error 8 ms 980 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 360 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 213 ms 468 KB Output is correct
5 Correct 149 ms 468 KB Output is correct
6 Correct 367 ms 468 KB Output is correct
7 Correct 222 ms 472 KB Output is correct
8 Correct 183 ms 448 KB Output is correct
9 Correct 204 ms 468 KB Output is correct
10 Correct 70 ms 440 KB Output is correct
11 Correct 67 ms 448 KB Output is correct
12 Correct 62 ms 392 KB Output is correct
13 Correct 120 ms 444 KB Output is correct
14 Correct 92 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Runtime error 10 ms 852 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -