oj.uz

Submission #48277

# Submission time Handle Problem Language Result Execution time Memory
48277 2018-05-11T10:15:03 Z Extazy Adriatic (CEOI13_adriatic) C++17
0 / 100
 2000 ms 11716 KB 
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 250007;
const pair < int, int > NEUTRAL = make_pair(-1,-1);

int n;
int dist[N];
bool used[N];
vector < int > v[N];
pair < int, int > a[N];

int bfs(int start) {
  int ans=0,i,curr;
  queue < int > q;

  fill(used+1,used+1+n,false);
  dist[start]=0;
  used[start]=true;
  q.push(start);

  while(!q.empty()) {
    curr=q.front();
    q.pop();

    for(i=0;i<(int)(v[curr].size());i++) if(!used[v[curr][i]]) {
      used[v[curr][i]]=true;
      dist[v[curr][i]]=dist[curr]+1;
      q.push(v[curr][i]);
    }
  }

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

  return ans;
}

void add_edge(int x, int y) {
  v[x].push_back(y);
  v[y].push_back(x);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int i,j,idx1,idx2,idx3,idx4;
  pair < int, int > a1,a2,a3,a4;

  scanf("%d", &n);
  for(i=1;i<=n;i++) {
    scanf("%d %d", &a[i].first, &a[i].second);
  }

  for(i=1;i<=n;i++) {
    pair < int, int > a1(NEUTRAL),a2(NEUTRAL),a3(NEUTRAL),a4(NEUTRAL);
    int idx1=-1,idx2=-1,idx3=-1,idx4=-1;

    for(j=1;j<=n;j++) {
      if(a[j].first<a[i].first && a[j].second<a[i].second) {
        if(a1==NEUTRAL) {
          a1=a[j];
          a2=a[j];
          idx1=j;
          idx2=j;
        }
        else {
          if(a[j].first<a1.first) {
            a1=a[j];
            idx1=j;
          }
          if(a[j].second<a2.second) {
            a2=a[j];
            idx2=j;
          }
        }
      }
      else if(a[j].first>a[i].first && a[j].second>a[i].second) {
        if(a3==NEUTRAL) {
          a3=a[j];
          a4=a[j];
          idx3=j;
          idx4=j;
        }
        else {
          if(a[j].first>a3.first) {
            a3=a[j];
            idx3=j;
          }
          if(a[j].second>a4.second) {
            a4=a[j];
            idx4=j;
          }
        }
      }
    }

    if(idx1!=-1) add_edge(i,idx1);
    if(idx2!=-1) add_edge(i,idx2);
    if(idx3!=-1) add_edge(i,idx3);
    if(idx4!=-1) add_edge(i,idx4);
  }

  for(i=1;i<=n;i++) {
    printf("%d\n", bfs(i));
  }

  return 0;
}

Compilation message

adriatic.cpp: In function 'int main()':
adriatic.cpp:50:11: warning: unused variable 'idx1' [-Wunused-variable]
   int i,j,idx1,idx2,idx3,idx4;
           ^~~~
adriatic.cpp:50:16: warning: unused variable 'idx2' [-Wunused-variable]
   int i,j,idx1,idx2,idx3,idx4;
                ^~~~
adriatic.cpp:50:21: warning: unused variable 'idx3' [-Wunused-variable]
   int i,j,idx1,idx2,idx3,idx4;
                     ^~~~
adriatic.cpp:50:26: warning: unused variable 'idx4' [-Wunused-variable]
   int i,j,idx1,idx2,idx3,idx4;
                          ^~~~
adriatic.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
adriatic.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &a[i].first, &a[i].second);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 6392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 6516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1226 ms 7108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2037 ms 8176 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2053 ms 11716 KB Time limit exceeded
2 Halted 0 ms 0 KB -