Submission #48315

#	Time	Username	Problem	Language	Result	Execution time	Memory
48315		Extazy	Adriatic (CEOI13_adriatic)	C++17	60 / 100	2077 ms	8636 KiB

adriatic

#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 (stderr)

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 / 25
• Subtask 2: 25 / 25
• Subtask 3: 10 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20