oj.uz

Submission #756116

# Submission time Handle Problem Language Result Execution time Memory
756116 2023-06-11T06:56:10 Z VadimK Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 15608 KB 
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main()
{
    int n,m;
    cin>>n>>m;
    string ans="";
    ll s[n+1];
    vector <ll> g[n+1];
    for (int i=1; i<=n; i++)
        cin>>s[i];
    for (int i=1; i<=m; i++)
    {
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    priority_queue <pair<ll,ll> > q;
    for (int i=1; i<=n; i++)
    {
        ll total=s[i];
        ll v,num;
        bool vis[n+1]= {0},can=1;
        vis[i]=1;
        q.push(make_pair(0,i));
        while (!q.empty())
        {
            tie (num,v)=q.top();
            q.pop();
            num*=-1;
            if (total<num) {can=0; break;}
            total+=num;
            for (int j=0; j<g[v].size(); j++)
                if (!vis[g[v][j]]) {q.push(make_pair(-1*s[g[v][j]],g[v][j])); vis[g[v][j]]=1;}
        }
        for (int x=1; x<=n; x++)
            if (!vis[x])
                {can=0; break;}
        if (can==1) ans+='1';
        else ans+='0';
        while (!q.empty()) q.pop();
    }
  cout<<ans;
}

Compilation message

island.cpp: In function 'int main()':
island.cpp:37:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             for (int j=0; j<g[v].size(); j++)
      |                           ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 171 ms 468 KB Output is correct
5 Correct 177 ms 448 KB Output is correct
6 Correct 236 ms 436 KB Output is correct
7 Correct 165 ms 444 KB Output is correct
8 Correct 108 ms 340 KB Output is correct
9 Correct 283 ms 476 KB Output is correct
10 Correct 76 ms 452 KB Output is correct
11 Correct 68 ms 440 KB Output is correct
12 Correct 64 ms 468 KB Output is correct
13 Correct 109 ms 424 KB Output is correct
14 Correct 117 ms 456 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Execution timed out 1016 ms 13684 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 300 KB Output is correct
2 Execution timed out 1087 ms 15248 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 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 171 ms 468 KB Output is correct
5 Correct 177 ms 448 KB Output is correct
6 Correct 236 ms 436 KB Output is correct
7 Correct 165 ms 444 KB Output is correct
8 Correct 108 ms 340 KB Output is correct
9 Correct 283 ms 476 KB Output is correct
10 Correct 76 ms 452 KB Output is correct
11 Correct 68 ms 440 KB Output is correct
12 Correct 64 ms 468 KB Output is correct
13 Correct 109 ms 424 KB Output is correct
14 Correct 117 ms 456 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Execution timed out 1073 ms 15608 KB Time limit exceeded
18 Halted 0 ms 0 KB -