Submission #640240

#	Time	Username	Problem	Language	Result	Execution time	Memory
640240		devariaota	Stranded Far From Home (BOI22_island)	C++17	20 / 100	262 ms	34668 KiB

island

#include <bits/stdc++.h>
using namespace std;

#define nyahalo ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define otsumiko exit(0);
#define mikodanye priority_queue<pair<long long, long long>, vector<pair<long long, long long> >, greater<pair<long long, long long> > >
#define mikochi priority_queue<long long, vector<long long>, greater<long long> >

long long n, m, s[200069], a, b, vd[200069], cs, nov, nn, cv, cn, sb2 = 1, tn, pv[200069], dp[200069], z[200069], pi;
vector<long long> al[200069];
mikodanye pq;

void dfs(long long cn, long long pn) {
  long long i, j, nn;
  pv[cn] = pn;
  dp[cn] = s[cn];
  for (i=0; i<al[cn].size(); i++) {
    nn = al[cn][i];
    if (nn == pn) {
      continue;
    }
    dfs(nn, cn);
    dp[cn] += dp[nn];
  }
}

int main() {
  nyahalo
  long long i, j;
  cin >> n >> m;
  for (i=1; i<=n; i++) {
    cin >> s[i];
    if (i>1) {
      if (s[i]>s[i-1]) {
        sb2 = 0;
      }
    }
  }
  for (i=1; i<=m; i++) {
    cin >> a >> b;
    al[a].push_back(b);
    al[b].push_back(a);
  }
  for (i=2; i<=n; i++) {
    tn = 0;
    for (j=0; j<al[i].size(); j++) {
      cn = al[i][j];
      if (cn<i) {
        tn++;
      }
    }
    if (tn != 1) {
      sb2 = 0;
      break;
    }
  }
  if (n<=2000 && m<=2000) {
    for (i=1; i<=n; i++) {
      for (j=1; j<=n; j++) {
        vd[j] = 0;
      }
      nov = 0;
      cs = 0;
      pq.push(make_pair(s[i], i));
      vd[i] = 1;
      for (; !pq.empty(); ) {
        cv = pq.top().first;
        cn = pq.top().second;
        pq.pop();
        if (cs<cv && cn != i) {
          break;
        }
        nov++;
        cs += cv;
        for (j=0; j<al[cn].size(); j++) {
          nn = al[cn][j];
          if (vd[nn] == 0) {
            vd[nn] = 1;
            pq.push(make_pair(s[nn], nn));
          }
        }
      }
      for (; !pq.empty(); ) {
        pq.pop();
      }
      if (nov == n) {
        cout << "1";
      } else {
        cout << "0";
      }
    }
    cout << "\n";
    otsumiko
  }
  if (sb2 == 1) {
    dfs(1, -1);
    z[1] = 1;
    for (i=2; i<=n; i++) {
      pi = pv[i];
      if (dp[i]>=s[pi] && z[pi] == 1) {
        z[i] = 1;
      } else {
        z[i] = 0;
      }
    }
    for (i=1; i<=n; i++) {
      cout << z[i];
    }
    cout << "\n";
    otsumiko
  }
  cout << "sabar deck\n";
  otsumiko
}

Compilation message (stderr)

island.cpp: In function 'void dfs(long long int, long long int)':
island.cpp:17:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   for (i=0; i<al[cn].size(); i++) {
      |             ~^~~~~~~~~~~~~~
island.cpp:14:16: warning: unused variable 'j' [-Wunused-variable]
   14 |   long long i, j, nn;
      |                ^
island.cpp: In function 'int main()':
island.cpp:46:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (j=0; j<al[i].size(); j++) {
      |               ~^~~~~~~~~~~~~
island.cpp:75:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for (j=0; j<al[cn].size(); j++) {
      |                   ~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35