oj.uz

Submission #48315

# Submission time Handle Problem Language Result Execution time Memory
48315 2018-05-11T16:46:17 Z Extazy Adriatic (CEOI13_adriatic) C++17
60 / 100
 2000 ms 8636 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);

  for(i=1;i<=n;i++) {
    if((a[i].first>a[start].first && a[i].second>a[start].second) || (a[i].first<a[start].first && a[i].second<a[start].second)) {
      used[i]=true;
      dist[i]=1;
      q.push(i);
    }
  }

  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 || (a[j].first==a1.first && a[j].second<a1.second)) {
            a1=a[j];
            idx1=j;
          }
          if(a[j].second<a2.second || (a[j].first==a2.first && 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 || (a[j].first==a3.first && a[j].second>a3.second)) {
            a3=a[j];
            idx3=j;
          }
          if(a[j].second>a4.second || (a[j].first==a4.first && 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:58:11: warning: unused variable 'idx1' [-Wunused-variable]
   int i,j,idx1,idx2,idx3,idx4;
           ^~~~
adriatic.cpp:58:16: warning: unused variable 'idx2' [-Wunused-variable]
   int i,j,idx1,idx2,idx3,idx4;
                ^~~~
adriatic.cpp:58:21: warning: unused variable 'idx3' [-Wunused-variable]
   int i,j,idx1,idx2,idx3,idx4;
                     ^~~~
adriatic.cpp:58:26: warning: unused variable 'idx4' [-Wunused-variable]
   int i,j,idx1,idx2,idx3,idx4;
                          ^~~~
adriatic.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
adriatic.cpp:63: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
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6264 KB Output is correct
2 Correct 6 ms 6264 KB Output is correct
3 Correct 6 ms 6316 KB Output is correct
4 Correct 7 ms 6316 KB Output is correct
5 Correct 6 ms 6348 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 6356 KB Output is correct
2 Correct 100 ms 6484 KB Output is correct
3 Correct 101 ms 6528 KB Output is correct
4 Correct 97 ms 6528 KB Output is correct
5 Correct 99 ms 6576 KB Output is correct
6 Correct 78 ms 6576 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1179 ms 7112 KB Output is correct
2 Correct 1041 ms 7112 KB Output is correct
3 Correct 1227 ms 7112 KB Output is correct
4 Correct 1039 ms 7112 KB Output is correct
5 Correct 1061 ms 7112 KB Output is correct
6 Correct 910 ms 7112 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2065 ms 7256 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 2077 ms 8636 KB Time limit exceeded
2 Halted 0 ms 0 KB -