Submission #1276318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276318		quanaskinger	Matryoshka (JOI16_matryoshka)	C++17	26 / 100	2 ms	588 KiB

matryoshka

#include<bits/stdc++.h>
using namespace std;
long long n, q;
vector <long long> v[2105];
pair<long long, long long> e[2105];
bool check[2105], conceived[2105];
pair<long long, long long> arr[2105];
long long x, y, w;
bool cmp(long long x, long long y) {
 return arr[x].first < arr[y].first;
}
void dfs(long long x)
{
 check[x] = 1;
    for (long long i = 0; i < v[x].size(); i++)
    {
        if (!check[v[x][i]] && conceived[v[x][i]] && arr[v[x][i]].first > arr[x].first && arr[v[x][i]].second > arr[x].second)
        {
            check[v[x][i]] = true;
            dfs(v[x][i]);
            break;
        }
    }
}
int main() {
 cin >> n >> q;
 for (long long i = 1; i <= n; i++) cin >> arr[i].first >> arr[i].second;
 for (long long i = 1; i <= n; i++) {
  for (long long j = 1; j <= n; j++) {
   if (arr[i].first < arr[j].first && arr[i].second < arr[j].second) {
    v[i].push_back(j);
    v[j].push_back(i);
   }
  }
 }
 for (long long i = 1; i <= n; i++) {
  sort(v[i].begin(), v[i].end(), cmp);
 }
 while (q--) {
  cin >> x >> y;
  memset(check, 0, sizeof(check));
  memset(conceived, 0, sizeof(conceived));
  vector <long long> cor;
  for (long long i = 1; i <= n; i++) {
   if (arr[i].first >= x && arr[i].second <= y) {
    conceived[i] = 1;
    cor.push_back(i);
   }
  }
  w = 0;
  sort(cor.begin(), cor.end(), cmp);
  for (auto x: cor) {
   if (!check[x]) {
    w++;
    dfs(x);
   }
  }
  cout << w << "\n";
  
 }
}

• Subtask 1: 11 / 11
• Subtask 2: 15 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 49