oj.uz

Submission #1050535

# Submission time Handle Problem Language Result Execution time Memory
1050535 2024-08-09T10:35:11 Z sofijavelkovska Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 14356 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=2e5;

int n, m;
int a[MAXN];
vector<int> adj[MAXN];
long long prefix[MAXN];

bool compare(int x, int y)
{
    return a[x]>a[y];
}

long long sum(int l, int r)
{
    if (l==0)
        return prefix[r];

    return prefix[r]-prefix[l-1];
}

vector<bool> brute()
{
    vector<bool> possible(n, 0);
    for (int i=0; i<n; i++)
    {
        priority_queue<pair<int, int> > pq;
        pq.push({-a[i], i});
        long long sum=0;
        bool visited[n]={false};
        while (!pq.empty())
        {
            int x=pq.top().second;
            pq.pop();
            if (x!=i && sum<a[x])
                continue;
            if (visited[x])
                continue;
            visited[x]=true;
            sum=sum+a[x];
            for (auto y : adj[x])
                if (!visited[y])
                    pq.push({-a[y], y});
        }
        if (*min_element(visited, visited+n)==1)
            possible[i]=true;
    }

    return possible;
    /*vector<bool> possible(n, 0);
    for (int i=0; i<n; i++)
    {
        long long sum=a[i];
        int l=i, r=i;
        while (true)
        {
            if (l>0 && sum>=a[l-1])
            {
                sum=sum+a[l-1];
                l=l-1;
            }
            else if (r<n-1 && sum>=a[r+1])
            {
                sum=sum+a[r+1];
                r=r+1;
            }
            else
                break;
        }
        if (l==0 && r==n-1)
            possible[i]=true;
    }

    return possible;*/
}

int main()
{
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);

    cin >> n >> m;
    for (int i=0; i<n; i++)
        cin >> a[i];
    for (int i=0; i<m; i++)
    {
        int x, y;
        cin >> x >> y;
        x=x-1;
        y=y-1;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    auto br=brute();
    for (int i=0; i<n; i++)
        cout << br[i];
    return 0;

    srand(time(0));
    int tc=0;
    //cin >> tc;
    while (true)
    {
        tc=tc+1;
        cout << "tc " << tc << '\n';
        n=rand()%20+1, m=0;
        for (int i=0; i<n; i++)
            a[i]=rand()%20+1;
        //for (int i=0; i<n; i++)
          //  cout << a[i] << ' ';
        //cout << '\n';

    //cin >> n >> m;
    //for (int i=0; i<n; i++)
      //  cin >> a[i];
    for (int i=0; i<n-1; i++)
    {
        adj[i].push_back(i+1);
        adj[i+1].push_back(i);
    }
    for (int i=0; i<m; i++)
    {
        int x, y;
        cin >> x >> y;
    }
    int sorted[n];
    for (int i=0; i<n; i++)
        sorted[i]=i;
    sort(sorted, sorted+n, compare);
    int possible[n]={false};
    possible[sorted[0]]=true;
    set<int> larger;
    larger.insert(sorted[0]);
    prefix[0]=a[0];
    for (int i=1; i<=n; i++)
        prefix[i]=prefix[i-1]+a[i];
    for (int i=1; i<n; i++)
    {
        int x=sorted[i];
        int l=-1, r=n;
        auto it=larger.lower_bound(x);
        if (it!=larger.end())
            r=*it;
        if (it!=larger.begin())
        {
            it--;
            l=*it;
        }
        if (l!=-1 && possible[l] && sum(l+1, r-1)>=a[l])
            possible[x]=true;
        if (r!=n && possible[r] && sum(l+1, r-1)>=a[r])
            possible[x]=true;
        larger.insert(x);
    }

        auto br=brute();
        bool flop=false;
        for (int i=0; i<n; i++)
            if (possible[i]!=br[i])
                flop=true;
        //if (flop)
        {
            cout << "FLOP\n";
            cout << n << '\n';
            for (int i=0; i<n; i++)
                cout << a[i] << ' ';
            cout << '\n';
            for (int i=0; i<n; i++)
                cout << possible[i];
            cout << '\n';
            for (int i=0; i<n; i++)
                cout << br[i];
            cout << '\n';
            //break;
        }
    }

    return 0;
}

Compilation message

island.cpp: In function 'int main()':
island.cpp:159:14: warning: variable 'flop' set but not used [-Wunused-but-set-variable]
  159 |         bool flop=false;
      |              ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 150 ms 5212 KB Output is correct
5 Correct 94 ms 6492 KB Output is correct
6 Correct 210 ms 6632 KB Output is correct
7 Correct 144 ms 6664 KB Output is correct
8 Correct 108 ms 5208 KB Output is correct
9 Correct 191 ms 5208 KB Output is correct
10 Correct 39 ms 6492 KB Output is correct
11 Correct 38 ms 6488 KB Output is correct
12 Correct 33 ms 6488 KB Output is correct
13 Correct 67 ms 5212 KB Output is correct
14 Correct 77 ms 5212 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Execution timed out 1098 ms 14356 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Execution timed out 1090 ms 13792 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 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 150 ms 5212 KB Output is correct
5 Correct 94 ms 6492 KB Output is correct
6 Correct 210 ms 6632 KB Output is correct
7 Correct 144 ms 6664 KB Output is correct
8 Correct 108 ms 5208 KB Output is correct
9 Correct 191 ms 5208 KB Output is correct
10 Correct 39 ms 6492 KB Output is correct
11 Correct 38 ms 6488 KB Output is correct
12 Correct 33 ms 6488 KB Output is correct
13 Correct 67 ms 5212 KB Output is correct
14 Correct 77 ms 5212 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Execution timed out 1098 ms 14356 KB Time limit exceeded
18 Halted 0 ms 0 KB -