Submission #1220078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220078		comgaTramAnh	Regions (IOI09_regions)	C++17	85 / 100	8064 ms	33424 KiB

regions

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <utility> 
#include <math.h>
int n, R, numQueries;
int timeDfs = 0;  
int f[1205][25005]; 
int id[25005]; 
std::vector <int> adj[200005]; 
int home[200005]; 
int cnt[25005]; 
int numb[25005];
int l[200005], r[200005]; 
std::vector <int> listTime[25005];  
std::vector <std::pair <int, int>> save;
std::vector <int> heavy, light;
std::vector <int> listVertex[25005];  
void dfs(int u, int father) {
  for (int i = 0; i < (int) heavy.size(); i++) {
    f[id[heavy[i]]][id[home[u]]] += numb[home[u]];  
  }
  numb[home[u]]++; 
  for (int i = 0; i < (int) adj[u].size(); i++) {
    int v = adj[u][i];
    if (v == father) {
      continue; 
    }
    dfs(v, u); 
  }                            
  numb[home[u]]--; 
}
void euler_tour(int u, int father) {
  timeDfs++;
  l[u] = timeDfs;
  listTime[home[u]].push_back(l[u]); 
  for (int i = 0; i < (int) adj[u].size(); i++) {
    int v = adj[u][i];
    if (v == father) {
      continue; 
    }
    euler_tour(v, u); 
  }  
  r[u] = timeDfs; 
}
int main() {
  scanf("%d %d %d", &n, &R, &numQueries);
  scanf("%d", &home[1]);
  for (int i = 2; i <= n; i++) {
    int parent;
    scanf("%d %d", &parent, &home[i]); 
    adj[parent].push_back(i);
  }
  for (int i = 1; i <= n; i++) {
    cnt[home[i]]++;  
    listVertex[home[i]].push_back(i); 
  }
  for (int i = 1; i <= R; i++) {
    save.push_back(std::make_pair(cnt[i], i)); 
  }
  std::sort(save.begin(), save.end());
  std::reverse(save.begin(), save.end()); 
  const int block = 500;
  for (int i = 1; i <= R; i++) {
    id[i] = -1; 
  }
  for (int i = 0; i < (int) save.size(); i++) {
    if (id[save[i].second] != -1) {
      continue;
    }
    id[save[i].second] = i;
    if (save[i].first >= block) {
      heavy.push_back(save[i].second); 
    }
    else {
      light.push_back(save[i].second); 
    }  
  }
  for (int i = 1; i <= R; i++) {
    cnt[i] = 0; 
  }
  dfs(1, -1);
  timeDfs = 0;
  euler_tour(1, -1);
  for (int query = 1; query <= numQueries; query++) {
    int r1, r2;
    scanf("%d %d", &r1, &r2);  
    if (cnt[r1] >= block) {
      printf("%d\n", f[id[r1]][id[r2]]);           
    }
    else {
      std::vector <int> &vec = listVertex[r1]; 
      std::vector <int> &vTime = listTime[r2];
      int ans = 0; 
      for (int i = 0; i < (int) vec.size(); i++) {
        int u = vec[i]; 
        std::vector <int>::iterator it1 = std::lower_bound(vTime.begin(), vTime.end(), l[u]); 
        std::vector <int>::iterator it2 = std::upper_bound(vTime.begin(), vTime.end(), r[u]);
        ans += it2 - it1;
      }
      printf("%d\n", ans); 
    }
    fflush(stdout); 
  }            
  return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   scanf("%d %d %d", &n, &R, &numQueries);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   scanf("%d", &home[1]);
      |   ~~~~~^~~~~~~~~~~~~~~~
regions.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf("%d %d", &parent, &home[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     scanf("%d %d", &r1, &r2);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 70 / 85